Tak, E = NE oznacza EXP = NEXP, co można udowodnić za pomocą argumentu wypełniającego.
Mohammad Al-Turkistany
11
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 2 O ( n ) -to-czasowy dla Succinct3SAT. Może zmieniłeś sytuację i chciałeś zapytać o inne implikacje? 2)nk2)O ( n )
Ryan Williams
2
A następnie P = NP, jeśli P = 0 lub N = 1!
Daniel Apon
1
Tak. Myślę, że to problem z pracą domową.
Mohammad Al-Turkistany
6
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
Odpowiedzi:
19
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 2 O ( n ) -to-czasowy dla Succinct3SAT.2)nk2)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 NR E X P = E X P ) lub jego przeciwieństwo „rozdzielenie w dół”.P.= NP.N.miXP.= EXP.
Coś podobnego do tego, czego chcesz, to twierdzenie Hartmanisa, Immermana i Sewelsona ( http://dl.acm.org/citation.cfm?id=808769 ), że N.mi= E⟺każdy rzadki ustawione w jest zawarty w P . Daje to „załamanie w dół”, ale tylko dla rzadkich zestawów (tych zestawów, które zawierają tylko p o l y ( n ) ciągów o długości n ).N.P.P.p o l y( n )n
Odpowiedzi:
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 2 O ( n ) -to-czasowy dla Succinct3SAT.2)nk 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 NR E X P = E X P ) lub jego przeciwieństwo „rozdzielenie w dół”.P.= NP. N.miXP.= EXP.
Coś podobnego do tego, czego chcesz, to twierdzenie Hartmanisa, Immermana i Sewelsona ( http://dl.acm.org/citation.cfm?id=808769 ), żeN.mi= E ⟺ każdy rzadki ustawione w jest zawarty w P . Daje to „załamanie w dół”, ale tylko dla rzadkich zestawów (tych zestawów, które zawierają tylko p o l y ( n ) ciągów o długości n ).N.P. P. p o l y( n ) n
źródło