Konsekwencje

12

Wiemy, że jeśli wówczas całe PH załamuje się. Co się stanie, jeśli hierarchia wielomianowa ulegnie częściowemu zawaleniu? (Lub jak zrozumieć, że PH może spaść powyżej pewnego punktu, a nie poniżej?)P=NP

Krótko mówiąc, jakie byłyby konsekwencje i P N P ?NP=coNPPNP

Xavier Labouze
źródło
3
W takim przypadku PH nadal spada (do 1., a nie do 0. poziomu).
Huck Bennett,
Pierwsze zdanie wydaje się wyrażać, że „mamy kłopoty, jeśli P = NP nie jest spowodowane upadkiem hierarchii”, co nie jest poprawne (odkładając na bok prawdopodobnie kontrowersyjne pytanie, czy P = NP jest kłopotliwą sytuacją).
Kaveh
2
@Huck Myślę, że OP może próbować zapytać, jakie są konsekwencje załamania PH na 1. poziom. Jakie fajne problemy moglibyśmy wtedy rozwiązać?
Artem Kaznatcheev
@Xavier: Dlaczego mówisz „... a my mamy kłopoty” . P = NP, a co za tym idzie załamanie PH, byłoby po prostu fantastyczne ;-)
Giorgio Camerani,
@ArtemKaznatcheev: dziękuję za zrozumienie komentarz
Xavier Labouze,

Odpowiedzi:

17

Dla mnie jedną z najbardziej podstawowych i zaskakujących konsekwencji jest istnienie krótkich dowodów dla całego szeregu problemów, w których bardzo trudno jest zrozumieć, dlaczego powinny mieć krótkie dowody. (Jest to rodzaj cofnięcia się od „Jakie inne implikacje złożoności ma to załamanie?” Do „Jakie są podstawowe, przyziemne powody tego zawalenia się byłyby zaskakujące?”)NP=coNP

Na przykład, jeśli , to dla każdego wykresu, który nie jest hamiltonianem, istnieje krótki dowód tego faktu. Podobnie w przypadku wykresów, które nie są trójkolorowe. Podobnie dla par wykresów, które nie są izomorficzne. Podobnie w przypadku każdej tautologii zdań .NP=coNP

W świecie, w którym , trudność w udowodnieniu tautologii zdań nie polega na tym, że niektóre krótkie tautologie mają długie dowody - ponieważ w takim świecie każda tautologia ma dowód wielomianowo krótki - ale raczej, że istnieją pewne inny powód, dla którego nie jesteśmy w stanie skutecznie znaleźć tych dowodów.PNP=coNP

Joshua Grochow
źródło
Podoba mi się ta odpowiedź! +1
Tayfun Zapłać
Tks za twoją odpowiedź, podkreślona konsekwencja jest dość zaskakująca. Zastanawiam się, jaki inny powód nie jest w stanie skutecznie znaleźć tych dowodów. Dowolny pomysł ?
Xavier Labouze
12

Gdybyśmy również przyjęli , wówczas hipoteza spowodowałaby również upadek klas zrandomizowanych:NP=RPZPP=RP=CoRP=BPPPNP=coNP

BPPPNP=coNPENEPHPBPP=PBPPPPNP=coNPPH=NPNPPNPPENE

NP=coNPBPPPENEBPP=P

Andras Farago
źródło
1
Może jestem tutaj powolny, ale w jaki sposób NP = coNP oznacza ZPP = RP = coRP = BPP?
Joshua Grochow
@JoshuaGrochow Utknąłem też w tym.
Tayfun Zapłać
Dziękuję, rzeczywiście brakowało mi warunku. Poprawiłem odpowiedź.
Andras Farago
@AndrasFarago w porządku! +1 :)
Tayfun Zapłać
@AndrasFarago Tks za odpowiedź!
Xavier Labouze
7

#P

ValiantsDefinition:_C#C=AC(#P)A(#PA)A

#NP=#CoNP

TodasDefinition:_C#.CfCRpxf(x)=||{y|p(|x|)=|y|R(x,y)}||

#.NP=#.CoNPNP=CoNP

PNPFP#P

Tayfun Pay
źródło
To jest wersja licząca NP.
Tayfun Pay
Do czego odnosi się ten okres w „# .NP”?
Timothy Sun
4
Istnieją dwa typy, jeśli zdefiniowano hierarchie zliczania. Jeden Valiant w 1979 roku i używa zapisu #P, # NP, # Co-NP ... Gdzie # NP = Co-NP. Z drugiej strony Toda zdefiniował inną hierarchię. A do tego notacja używa kropek. I # .NP! = #. Co-NP, chyba że NP = Co-NP
Tayfun Zapłać
2

Ker-i Ko Pokazał, że istnieje wyrocznia, która powoduje załamanie PH na poziomie k-tym. Patrz „Ker-I Ko: Relatywizowane hierarchie czasu wielomianu posiadające dokładnie poziomy K. SIAM J. Comput. 18 (2): 392-408 (1989)”.

Bin Fu
źródło
Czy możesz połączyć nas z gazetą?
Tayfun Zapłać
@ BinFu Tks - Myślałem, że PH upada na pierwszy poziom ...
Xavier Labouze
1
W przypadku k = 1 jest to przypadek tego problemu. Czas wielomianowy zapada się do NP pod warunkiem, że NP = coNP. Istnienie wyroczni dla K-tego poziomu w papierze Ko oznacza barierę dla każdej relatywnej metody radzenia sobie z problemem zapadania się PH.
Bin Fu
1
@BinFu: twoje uwagi nie opisują żadnych konsekwencji PNP = coNP . Pytanie nie polegało na tym, jak pokazać upadek na pierwszym poziomie, ani na wynikach, które również opisują upadek na pierwszym poziomie, ale na tym, co można by nazwać następstwem upadku na pierwszy poziom. W ogóle nie rozumiem, jak na to wpływa twoja odpowiedź.
Niel de Beaudrap
1
Każda zadowalająca formuła boolowska ma wielomianowy dowód czasu i długości, który jest przypisaniem prawdy, aby formuła była prawdziwa. Warunek NP = coNP powoduje, że każda niezadowalająca formuła boolowska ma wielomianowy dowód czasu i długości. Jeśli P nie jest równe NP, a NP = coNP, to nie ma algorytmu czasu wielomianowego, który mógłby znaleźć dowód na wielomian długości dla wzoru boolowskiego na jego satysfakcję lub niezadowalanie. Podobnie będziemy mieli podobne wnioski dla wszystkich problemów w NP.
Bin Fu