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?)
Krótko mówiąc, jakie byłyby konsekwencje i P ≠ N P ?
cc.complexity-theory
complexity-classes
conditional-results
polynomial-hierarchy
Xavier Labouze
źródło
źródło
Odpowiedzi:
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.P≠NP=coNP
źródło
Gdybyśmy również przyjęli , wówczas hipoteza spowodowałaby również upadek klas zrandomizowanych:NP=RP ZPP=RP=CoRP=BPP P NP=coNP
źródło
źródło
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)”.
źródło