Pourrait-il y avoir un très grand sous-ensemble caché de problèmes résolus polynomialement dans les problèmes NP-Complete?

Supposons que P! = NP.

Nous savons que nous pouvons à tout moment créer des instances simples de 3-SAT. Nous pouvons également générer ce que nous pensons être des instances dures (car nos algorithmes ne peuvent pas les résoudre rapidement). Y a-t-il quelque chose qui empêche l'ensemble d'instances dures d'être arbitrairement petit, tant que pour une taille d'instance donnée (n), il n'y a que des instances Poly (n) (ou même constantes) de taille Poly (n) ou plus petite?

Pour toute instance 3-SAT dure, nous devrions ajouter l'ensemble de toutes les instances 3-SAT qu'elle réduit à via une boucle via le cycle de réduction NP-Completeness, mais je ne prévois pas que cela augmente le nombre d'instances hard. .

Dans ce monde, nous pourrions construire un algorithme qui résout polynomialement tous les problèmes NP complets, sauf quelques rares.

Edit: Une variante plus douce de la question: même si nous montrions P! = NP, comment pourrions-nous savoir si une méthode donnée pour générer des problèmes de taille n 3-SAT en a effectivement généré un avec une probabilité requise? S'il n'y a aucun moyen de savoir à partir de P! = NP seul, qu'est-ce qui est nécessaire pour montrer que nous pouvons générer un problème NP-complet difficile?

np-hardness p-vs-np Elliot JJ
la source

Oui. Les problèmes NP-complets sont difficiles dans le pire des cas. Il est possible que la majorité des cas d'un problème NP-complet soient efficacement résolubles. Cependant, Russell Impagliazzo a proposé un monde (Pessiland) où des problèmes NP-complets dans le cas moyen existent mais où les fonctions à sens unique n'existent pas. Dans ce monde, nous ne pouvons pas générer d'instances dures de problème NP-complet avec une solution connue.

Mohammad Al-Turkistany

Si l'ensemble d'instances dures de chaque longueur est polynomialement petit, alors NP est contenu dans P / poly. Il existe également d'autres façons de voir les choses, recherchez HeurP.

Kaveh

Cette question semble adresser votre modification - nous pouvons (determinstically) générer des instances difficiles de SAT si et seulement si unaire

unaire

N P \neq

$\mathsf{NP} \neq$

P

$\mathsf{P}$

usul

@ SarielHar-Peled En particulier, NP

P / poly réduit PH au deuxième niveau, ce qui est cohérent avec P! = NP.

\subseteq

$\subseteq$

Suresh Venkat

Il n'y a aucun moyen connu de connecter la dureté NP et la pire des cas. Cependant, il existe des moyens de connecter la dureté moyenne "légère" à la dureté moyenne "forte". Ma thèse est un point de départ pour les deux. ccs.neu.edu/home/viola/papers/thesis.pdf

Manu

Réponses:

$\mathsf{NP} \subseteq \mathsf{P/poly}$ $\mathsf{P} = \mathsf{NP}$ $\leq p(n)$ $n$ $q(n)$ $p$ $q$ $\mathsf{P} = \mathsf{NP}$ $poly(n)$ $n$ $\mathsf{P} \neq \mathsf{NP}$

$\mathsf{almostP}$ $\mathsf{BPP}$

$\mathsf{P} \neq \mathsf{NP}$ $p$ $p(n)$

$p(n)$

Joshua Grochow
la source

Personne n'a mentionné le fameux journal "Five worlds" d'Impagliazzo.

http://www.cs.ucsd.edu/users/russell/average.ps

aucun
la source

Cela a été référencé par le tout premier commentaire?

András Salamon

-3

$\stackrel{?}{=}$

Y a-t-il quelque chose qui empêche l'ensemble d'instances dures d'être arbitrairement petit, tant que pour une taille d'instance donnée (n), il n'y a que des instances Poly (n) (ou même constantes) de taille Poly (n) ou plus petite?

encore une fois, le théorème de Mahaney (formulé d'une manière légèrement différente) répond directement à cette question. une autre façon de voir les choses est que les tentatives de restreindre la distribution des instances d'une manière clé / caractéristique conduisent à des fonctions NP-complètes. un exemple de ceci de la complexité du circuit monotone est "les fonctions de tranche". [2]

[1] Prédire la satisfaction à la transition de phase Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

[2] Paul ES Dunne: La complexité des fonctions de tranche centrale. Théor. Comput. Sci. 44: 247 à 257 (1986)

[3] Solution analytique et algorithmique de problèmes de satisfaction aléatoires M. Mezard, G. Parisi, R. Zecchina

[4] Transitions de phase dans des problèmes NP-complets: un défi pour la probabilité, la combinatoire et l'informatique par Moore

vzn
la source