Czy można rozwiązać dowolny problem NP-Complete przy użyciu co najwyżej przestrzeni wielomianowej (ale przy użyciu czasu wykładniczego?)

Czytam o NPC i jego związku z PSPACE i chcę wiedzieć, czy problemy NPC można rozwiązać w sposób deterministyczny za pomocą algorytmu o najgorszym przypadku wymaganej przestrzeni wielomianowej, ale potencjalnie zajmującego wykładniczy czas (2 ^ P (n), gdzie P jest wielomianem).

Co więcej, czy można ją ogólnie uogólnić na EXPTIME ?

Powód, dla którego o to pytam, jest taki, że napisałem kilka programów do rozwiązywania zdegenerowanych przypadków problemu NPC i mogą one zużywać bardzo duże ilości pamięci RAM w przypadku trudnych instancji i zastanawiam się, czy istnieje lepszy sposób. W celach informacyjnych patrz https://fc-solve.shlomifish.org/faq.html .

Ogólnie rzecz biorąc, dla każdego algorytmu są spełnione następujące warunki:

1. Załóżmy, że jest algorytmem działającym w czasie . Następnie nie może mieć więcej niż przestrzeni od pisania bitów wymaga razem.$A$$f(n)$$A$$f(n)$$f(n)$$f(n)$
2. Załóżmy, że jest algorytmem wymagającym przestrzeni . Następnie za czas może odwiedzić każdy ze swoich różnych stanów, dlatego nie może nic zyskać, uruchamiając więcej niż czasu.$A$$f(n)$$2^{f(n)}$$A$$2^{f(n)}$

Wynika, że:

$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Statemement jest znany jako część relacji między klasami, jak pokazano na poniższym diagramie:

Wyjaśnienie jest proste: problem ma certyfikat długości wielomianowej . Algorytm testujący wszystkie możliwe certyfikaty jest algorytmem, który decyduje o w czasie .$Q$ $\in$ $\mathbf{NP}$$y$$Q$$\large 2^{n^{O(1)}}$

Wymagane miejsce to:

• $y$ (wielomian w )$n$
• miejsce wymagane do zweryfikowania . Ponieważ jest certyfikatem wielomianowym, można go zweryfikować w czasie wielomianowym, dlatego nie może wymagać więcej niż przestrzeni wielomianowej.$y$$y$

Ponieważ suma dwóch wielomianów jest również wielomianem, można określić za pomocą przestrzeni wielomianowej.$Q$

Przykład:

Załóżmy, że jest instancją 3-CNF na literałach , z klauzulami . Przypisanie to jakaś funkcja .$\varphi$$x_1 \dots x_n$$m$$f$$f:\{x_1\dots x_n\} \rightarrow \{0,1\}$

Utrzymuje, że:

• Istnieją różnych zadań.$2^n$
• Biorąc pod uwagę przypisanie , obliczenie wartości zajmuje , dlatego nie może wymagać więcej niż przestrzeni.$f$$O(m)$$\varphi$$O(m)$

Tak więc algorytm który sprawdza wszystkie możliwe przypisania, użyje przestrzeni wielomianowej, uruchomi się w czasie wykładniczym i zdecyduje 3-SAT.$A$

Wynika, że:

3-SAT , a ponieważ 3-SAT jest NP-Complete,$\in \mathbf{PSPACE}$$\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

Tak. Oto szkic bezpośredniego dowodu.

$\mathrm{NP}$$M$$p$$M$$n$$p(n)$$p(n)$

$c$$M$$M$$c$$c^{p(n)}$$n$$c^{p(n)}$$p(n)$$c$$p(n)$$M$$i$$i$$i$$6$

$0\dots 0$$M$$c-1$$c^{p(n)}p(n)$$2p(n)$