Lista twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy

Myślę, że dobrym pomysłem byłoby sporządzenie listy twierdzeń stwierdzających, że P nie jest równe NP wtedy i tylko wtedy, gdy takie i takie wyjścia, pewna klasa złożoności jest zawarta w innej klasie złożoności i tak dalej.

Oto jeden:

Twierdzenie Mahaneya: Nie ma rzadkiego zestawu NP-kompletnego wtedy i tylko wtedy, gdy (pod zmniejszeniem Karpa).$P \ne NP$

Kolejny to:

wtedy i tylko wtedy, gdy P ≠ P $P \ne NP$$P \ne PH$

wtedy i tylko wtedy, gdy istnieją funkcje jednokierunkowe w najgorszym przypadku.$P \ne NP$

Odniesienie:

Alan L. Selman. Przegląd funkcji jednokierunkowych w teorii złożoności. Teoria systemów matematycznych, 25 (3): 203–221, 1992.

Oto wynik opisowej teorii złożoności:

$P \ne NP$

Odniesienie: Immerman, Języki przechwytujące klasy złożoności

Twierdzenie Ladnera można sformułować jako:

$P \ne NP$$NP-P$

$NP$

Odniesienie

Teoria złożoności i kryptologia: wprowadzenie do kryptokompleksowości Jörg Rothe, strona 106