Dlaczego NP jest w EXPTIME?

Czy istnieje prosty sposób, aby dowiedzieć się, dlaczego NP jest w WYGODZIE? Wydaje mi się a priori możliwe, że może istnieć problem, który wymaga czasu nadwykładniczego do rozwiązania, ale którego rozwiązanie można zweryfikować w czasie wielomianowym.

complexity-theory complexity-classes

— tparker
źródło

W rzeczywistości NP

PSPACE.

\subseteq

$\subseteq$

Witamy w informatyce! Czego próbowałeś? Gdzie utknąłeś? Nie chcemy po prostu wykonywać dla ciebie pracy (domowej); chcemy, abyście zrozumieli. Ponieważ jednak nie wiemy, na czym polega Twój problem, nie możemy zacząć pomagać. Zobacz tutaj odpowiednią dyskusję. Jeśli nie jesteś pewien, jak poprawić swoje pytanie, dlaczego nie zapytać na czacie informatyki ? Możesz również sprawdzić nasze pytania referencyjne .

— Raphael

Każdy problem związany z NP występuje w trybie WYGODNY, ponieważ można użyć czasu wykładniczego do wypróbowania wszystkich możliwych certyfikatów lub do wyliczenia wszystkich możliwych ścieżek obliczeniowych maszyny niedeterministycznej.

Bardziej formalnie istnieją dwie główne definicje NP . Jednym z nich jest to, że język jest w NP iff istnieje relacja taka, że $L$ $R$

istnieje wielomian taki, że dla wszystkich , , $p$ $(x,y)\in R$ $|y|\leq p(|x|)$
biorąc pod uwagę ciąg , możemy wyznaczyć wielomian w czasie w czy , i $x\#y$ $|x\#y|$ $(x,y)\in R$
. $L = \{x\mid (x,y)\in R\}$

Więc jeśli mamy czas wykładniczy i chcemy wiedzieć, czy , możemy po prostu wypróbować wszystkie możliwe wartości dla ~ i sprawdź, czy dla którejkolwiek z nich. To zajmuje czas , więc $x\in L$ $|\Sigma|^{p(n)}$ $y$ $(x,y)\in R$ $2^{O(p(n))}$ $L\in\,$ EXPTIME .

Alternatywnie możemy zdefiniować NP jako zbiór języków ustalany przez niedeterministyczne wielomianowe maszyny Turinga. W takim przypadku, załóżmy, że o decyduje maszyna w czasie dla jakiegoś wielomianu , dla danych wejściowych o długości . Następnie sprawia, że co najwyżej niedeterministycznych wyborów przy ustalaniu, czy . Badając funkcję przejścia , możemy znaleźć stałą taką, że ma co najwyżej $L$ $M$ $p(n)$ $p$ $n$ $M$ $p(|x|)$ $x\in L$ $M$ $k$ $M$ niedeterministycznych wyborów na każdym etapie obliczeń (niezależnie od danych wejściowych), więc ma co najwyżej różnych sekwencji niedeterministycznych wyborów podczas odczytu wejścia . Biorąc pod uwagę wykładniczy czas, możemy symulować każdą z tych możliwości jedna po drugiej i sprawdzać, czy którakolwiek z nich akceptuje. $k$ $k^{p(|x|)} = 2^{O(p(|x|))}$ $x$

— David Richerby
źródło

Ściśle mówiąc, wielomian drugiego potrzeby pocisk wybiera się raz na zawsze, że nie może być zależny od

. ;)

x

$x$

y

$y$

— Martin Berger

Jaka jest dokładnie definicja EXPTIME? Pamiętam to jako

, ale twoja odpowiedź wydaje się zakładać

. Nie jest oczywiste, że można uwzględnić dodatkowy wielomian bez zmieniania go w inną klasę złożoności.

O (k^{| x |})

$O(k^{|x|})$

O (k^{p (| x |)})

$O(k^{p(|x|)})$

— kasperd

@kasperd Według Wikipedii, EXPTIME definiuje się jako problemy decyzyjne, które można rozwiązać w

O (k^{p (| x |)})

$O(k^{p(|x|)})$

— tparker 22.04.16