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