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 .

— Shlomi Fish
źródło

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

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)$
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}$

— wędzony łosoś
źródło

Dlaczego EXPSPACE i EXPTIME są powiązane? Myślałem, że czas i przestrzeń to różne zasoby. Jednym z przykładów, który przychodzi mi na myśl, jest złamanie schematu szyfrowania, który wymagałby WYŁĄCZENIA, ale stałej przestrzeni

— WeCanBeFriends

Intuicyjne jest to, że jeśli używasz spacji , musisz użyć przynajmniej czasu i nie powinieneś używać więcej niż czasu, ponieważ wtedy musisz ponownie odwiedzić te same stany. Właśnie dlatego PSPACE EXP

f (n)

$f(n)$

f (n)

$f(n)$

2^{f (n)}

$2^{f(n)}$

\subseteq

$\subseteq$

— lox

Czy f (n) różni się od O (n) w twoim przykładzie?

— WeCanBeFriends

@WeCanBeFriends Nie można stosować czasu wykładniczego ze stałą przestrzenią: potrzebujesz co najmniej miejsca używanego do zliczania do tej liczby wykładniczej (np. Licznik programu języka asemblera), który jest wielomianowy (logarytmiczny w wykładniczym)

— gigabajty

@gigabytes Nie wiemy tego. Najlepiej wiemy, że .

P \neq E X P T I M E

$P\not = EXPTIME$

— Tom van der Zanden,

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)$

— David Richerby
źródło