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

18

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.

cc.complexity-theory big-list p-vs-np

— Tayfun Pay
źródło

15

To byłby stały ułamek wszystkich dokumentów o złożoności!

— MCH

5

Powiedziałbym: „lista warunków implikujących P? NP”, ponieważ nie wszystkie te twierdzenia brzmią „jeśli i tylko jeśli”. Sądzę też, że ludzie są bardziej zainteresowani - ogólnie - wiedzą, jak udowodnić P? NP, dowodząc czegoś innego, niż wymienianiem wielu konsekwencji tego wyniku, tematem, który był szeroko omawiany gdzie indziej.

— Janoma,

2

@Janoma: jeśli chcesz ograniczyć się do implikacji, lista będzie naprawdę ogromna, biorąc pod uwagę ogromną liczbę wyników formularza: „Jeśli P! = NP, to problemu X nie można rozwiązać dokładnie / aproksymować przy stałym współczynniku w czasie wielomianowym ". Pytanie to powinno być o wiele bardziej skoncentrowane lub lepiej sformułowane, jeśli chcemy tego uniknąć.

— Anthony Labarre,

4

@Janoma: To nie rozwiązuje uzasadnionej troski Anthony'ego. Hipotezy implikujące P = NP są po prostu negacjami konsekwencji P consequences NP, a hipotezy implikujące P ly NP są negacjami konsekwencji P = NP. Jeśli SAT można rozwiązać w czasie wielomianowym, to P = NP. Jeśli Max3SAT jest przybliżony w czasie wielomianowym w stałym współczynniku mniejszym niż 8/7, to P = NP. I tak dalej.

— Tsuyoshi Ito,

7

@Janoma: „Jeśli X to P = NP” jest takie samo jak „Jeśli P ≠ NP, to nie-X”.

— Jeffε

11

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

— Mohammad Al-Turkistany
źródło

Może być to bardzo proste:

wtedy i tylko wtedy, gdy

.

P \neq N P

$P \ne NP$

F P \neq F N P

$FP \ne FNP$

— Mohammad Al-Turkistany

11

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.

— Mohammad Al-Turkistany
źródło

1

— sędzia

B P P \neq N P

$BPP \neq NP$

Tak jestem pewna. :) Zobacz referencje.

— Mohammad Al-Turkistany,

8

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

$P \ne NP$

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

— Mohammad Al-Turkistany
źródło

... na uporządkowanych konstrukcjach. W przeciwnym razie wiemy bezwarunkowo, że takie właściwości istnieją.

— Emil Jeřábek wspiera Monikę

@ EmilJeřábek tak, na uporządkowanych strukturach, jak to pośrednio założyła Immerman w powyższej pracy.

— Mohammad Al-Turkistany

7

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

— Mohammad Al-Turkistany
źródło