Liste des théorèmes indiquant que P n'est pas égal à NP si et seulement si

18

Je pense que ce serait une bonne idée de faire une liste de théorèmes indiquant que P n'est pas égal à NP si et seulement si telle ou telle sortie, une classe de complexité est contenue dans une autre classe de complexité et ainsi de suite et ainsi de suite.

cc.complexity-theory big-list p-vs-np Tayfun Pay
la source

15

Ce serait une fraction constante de tous les papiers de complexité!

MCH

5

Je dirais: "liste de conditions impliquant P? NP", car tous ces théorèmes ne sont pas "si et seulement si". De plus, je suppose que les gens sont plus intéressés - en général - à savoir comment prouver P? NP en prouvant autre chose, qu'à énumérer les nombreuses conséquences de ce résultat, un sujet qui a été largement discuté ailleurs.

Janoma

2

@Janoma: si vous voulez vous limiter aux implications, alors la liste sera vraiment énorme, étant donné l'énorme quantité de résultats du formulaire: "Si P! = NP, alors le problème X ne peut pas être résolu exactement / approximé dans un facteur constant en temps polynomial ". La question devrait être beaucoup plus ciblée ou mieux énoncée si nous voulons éviter cela.

Anthony Labarre

4

@Janoma: Cela ne résout pas la préoccupation bien fondée d'Anthony. Les hypothèses qui impliquent P = NP sont simplement des négations des conséquences de P ≠ NP, et les hypothèses qui impliquent P ≠ NP sont des négations des conséquences de P = NP. Si SAT est résoluble en temps polynomial, alors P = NP. Si Max3SAT est approximativement polynomial dans un facteur constant inférieur à 8/7, alors P = NP. Etc.

Tsuyoshi Ito

7

@Janoma: "Si X alors P = NP" est identique à "Si P ≠ NP alors pas-X".

Jeffε

11

En voici un:

Théorème de Mahaney: Il n'y a pas d'ensemble NP-clairsemé si et seulement si (sous réduction de Karp). $P \ne NP$

Un autre est:

si et seulement si $P \ne NP$ $P \ne PH$

Mohammad Al-Turkistany
la source

Peut - être cela est simple:

si et seulement si

.

P \neq N P

$P \ne NP$

F P \neq F N P

$FP \ne FNP$

Mohammad Al-Turkistany

11

si et seulement s'il existe des fonctions unidirectionnelles dans le pire des cas. $P \ne NP$

Référence:

Alan L. Selman. Un aperçu des fonctions à sens unique dans la théorie de la complexité. Théorie des systèmes mathématiques, 25 (3): 203-221, 1992.

Mohammad Al-Turkistany
la source

1

une référence serait bonne

vzn

Êtes-vous sûr? Je ne l' avais pas entendu parler de cas le plus défavorable owfs avant, mais des notes ici il semble que leur existence est équivalent à

.

B P P \neq N P

$BPP \neq NP$

Huck Bennett

Oui je suis sûr. :) Voir la référence.

Mohammad Al-Turkistany

8

Voici un résultat de la théorie de la complexité descriptive:

si et seulement si une propriété du second ordre n'est pas exprimable en utilisant la logique du premier ordre plus le point le moins fixe. $P \ne NP$

Référence: Immerman, Langages qui capturent les classes de complexité

Mohammad Al-Turkistany
la source

... sur les structures ordonnées. Sinon, nous savons sans condition que de telles propriétés existent.

Emil Jeřábek soutient Monica le

@ EmilJeřábek oui, sur les structures ordonnées comme cela a été implicitement supposé par Immerman dans le document ci-dessus.

Mohammad Al-Turkistany

7

Le théorème de Ladner peut être énoncé comme:

si et seulement s'il existe un ensemble incomplet dans $P \ne NP$ $NP-P$ .

Un ensemble incomplet est un ensemble qui n'est pas complet pour $NP$ sous plusieurs réductions de temps polynomiales.

Référence

Théorie de la complexité et cryptologie: une introduction à la cryptocomplexité Par Jörg Rothe, page 106

Mohammad Al-Turkistany
la source

Liste des théorèmes indiquant que P n'est pas égal à NP si et seulement si

Réponses: