Jeśli dolna granica problemu ma charakter wykładniczy, to czy jest to NP?

Zakładając, że mamy problem i pokazaliśmy, że dolną granicą rozwiązania jest . $p$ $p$ $\mathcal{\Omega}(2^n)$

czy dolna granica oznacza problem w ? $\mathcal{\Omega}(2^n)$ $NP$

time-complexity np-complete Kelalaka
źródło

To nie NP, ale trudne NP.

user35734,

Skąd wiesz, że to trudne NP?

Yuval Filmus,

Jeśli możesz wykazać, że problem występuje zarówno w i w NP, sprawdziłbyś, że P NP.

Ω (2^{n})

$\mathcal{\Omega}(2^n)$

\neq

$\neq$

kasperd

@kasperd: Nazywamy to układankami Merkle, ale należy je wyłączyć z P =? NP, ponieważ konkretna forma nie daje żadnych innych o takich samych właściwościach, a dowód P = NP w innym przypadku prawdopodobnie eliminuje jakikolwiek sposób tworzenia łamigłówek Merkle zamierzony. Czas wykładniczy Merkle's Puzzles to także PSPACE dla zamierzonego użytkownika.

Joshua,

Zagadki Joshuy Merkle'a nie są wykładnicze w zależności od długości wejściowej . (Cóż, jeśli założymy, że rozwiązanie dla Alicji jest wielomianowe).

rus9384,

Odpowiedzi:

Nie. Na przykład problem zatrzymania ma dolną granicę $\Omega(2^n)$ , ale nie ma go w NP (ponieważ nie jest obliczalny).

Twierdzenie o niedeterministycznej hierarchii czasu pokazuje, że każdy problem dotyczący NEXP-zupełności jest kolejnym przykładem (z $2^n$ potencjalnie zastąpionym przez mniejszą funkcję wykładniczą $c^{n^\epsilon}$ ).

NP jest górną granicą złożoności problemu.

Yuval Filmus
źródło

Czy możesz podać przykład problemu, który jest

ale nie NP-trudny?

Ω (2^{n})

$\Omega(2^n)$

Mario Carneiro,

Możesz skonstruować taki problem za pomocą diagonalizacji.

Yuval Filmus,

Przepraszam, nie śledzę. Co jest przekątne? Czy wyliczamy problemy lub algorytmy? Jak przebiega twardość inna niż NP?

Mario Carneiro,

Wymieniasz zarówno maszyny Turinga działające w czasie

i wielomianowe skrócenie czasu, upewniając się, że żaden z tych pierwszych nie oblicza twojego języka i żaden z tych drugich nie redukuje SAT do twojego języka.

2^{n}

$2^n$

Yuval Filmus,

Nie. Po pierwsze, jak zauważa Yuval , problem może być znacznie trudniejszy niż dolna granica, którą udowodniłeś.

Po drugie, nawet jeśli problem wymaga czasu $\Theta(2^n)$ do rozwiązania, nie wiemy, jak to odnosi się do $\mathbf{NP}$ . Możliwe, że $\mathbf{P}=\mathbf{NP}$ , w którym to przypadku jakikolwiek problem w $\mathrm{TIME}[\Omega(2^n)]$ pewnością nie występuje w $\mathbf{NP}$ według twierdzenia o hierarchii czasu. Ale nawet jeśli $\mathbf{P}\neq\mathbf{NP}$ , możliwe, że problem wymaga wykładniczy miejsca, więc nie jest w $\mathbf{NP}$ .

Najlepsze algorytmy wiemy na $\mathbf{NP}$ problemów -Complete wziąć wykładniczą czasu, ale nie należy zakładać, że „ $\mathbf{NP}$ ” oznacza „trwa wykładniczą czasu” i vice versa.

David Richerby
źródło