Czy

Czy oznacza ? $\mathsf{EXP}=\mathsf{NEXP}$ $\mathsf{E}=\mathsf{NE}$

— argentpepper
źródło

Tak, E = NE oznacza EXP = NEXP, co można udowodnić za pomocą argumentu wypełniającego.

— Mohammad Al-Turkistany

Nie jest dla mnie oczywiste, dlaczego EXP = NEXP oznacza E = NE. Jeśli to prawda, to dowolny algorytm

dla Succinct3SAT można przekonwertować na algorytm

-to-czasowy dla Succinct3SAT. Może zmieniłeś sytuację i chciałeś zapytać o inne implikacje?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

— Ryan Williams

A następnie P = NP, jeśli P = 0 lub N = 1!

— Daniel Apon

Tak. Myślę, że to problem z pracą domową.

— Mohammad Al-Turkistany

Nie rozumiem zamknięcia tego pytania jako „nie prawdziwego pytania” po tym, jak zostało zredagowane na rozsądne pytanie (chociaż treść pytania nie jest interesująca). Na przykład komentarz Ryana Williamsa może być odpowiedzią na to pytanie.

— Tsuyoshi Ito

O ile mi wiadomo, jest to otwarte. Może to być możliwe do udowodnienia (ponieważ jego hipoteza może być fałszywa) lub po prostu trudno jest wykazać, że dowolny algorytm dla Succinct3SAT można przekonwertować na algorytm -to-czasowy dla Succinct3SAT. $2^{n^k}$ $2^{O(n)}$

Ogólnie twierdzenia tego rodzaju nazywane są „upadkami w dół”, które mówią, że jeśli dwie „duże” klasy są równe, to dwie „mniejsze” klasy są równe. Te twierdzenia są rzadkie. Zwykle możesz albo udowodnić „załamanie w górę” (równe małe klasy oznaczają większe równe klasy, jak oznacza ) lub jego przeciwieństwo „rozdzielenie w dół”. $P = NP$ $NEXP = EXP$

Coś podobnego do tego, czego chcesz, to twierdzenie Hartmanisa, Immermana i Sewelsona ( http://dl.acm.org/citation.cfm?id=808769 ), że $NE = E$ $\iff$ każdy rzadki ustawione w jest zawarty w . Daje to „załamanie w dół”, ale tylko dla rzadkich zestawów (tych zestawów, które zawierają tylko ciągów o długości ). $NP$ $P$ $poly(n)$ $n$

— Ryan Williams
źródło