Konsekwencje

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=coNP$$P\ne NP$

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?”)$\mathsf{NP}=\mathsf{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ń .$\mathsf{NP}=\mathsf{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.$\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$

Gdybyśmy również przyjęli , wówczas hipoteza spowodowałaby również upadek klas zrandomizowanych:$\mathsf{NP}=\mathsf{RP}$$\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$

$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$$\,\,\mathsf{E}\neq \mathsf{NE}$$\mathsf{PH}$$\mathsf{P}$$\mathsf{BPP}=\mathsf{P}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{P}$$\mathsf{NP}=co\mathsf{NP}$$\mathsf{PH}=\mathsf{NP}$$\mathsf{NP}-\mathsf{P}$$\mathsf{NP}-\mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$

$\mathsf{NP}=co\mathsf{NP}$$\mathsf{BPP}\neq \mathsf{P}$$\mathsf{E}\neq \mathsf{NE}$$\mathsf{BPP}= \mathsf{P}$

${\bf \#P}$

${ \rm \underline {Valiant's-Definition:}}$$C$$\#C =\cup_{A\in C}(\#P)^{A}$$({\#P}^A)$$A$

${\bf \#NP} = {\bf \#CoNP}$

${ \rm \underline {Toda's-Definition:}}$$C$$\# .C$$f$$C-$$R$$p$$x$$f(x)=||\{y|p(|x|)=|y|$$R(x,y)\}||$

${\bf \#.NP} = {\bf \#.CoNP}$${\bf NP} = {\bf CoNP}$

${\bf P}\not = {\bf NP}$${\bf FP} \not = {\bf \# P}$

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)”.