Existe-t-il des problèmes complets de NP sans heuristique?

Existe-t-il des problèmes NP complets sans sous-ensemble infini d'instances telles que l'appartenance à peut être décidée en temps polynomial, et pour tout , peut être résolu en temps polynomial? (En supposant )$\Phi$$\Phi$$x \in \Phi$$x$$P \neq NP$

Voir la réponse de Josh Grochow au surensemble de temps Poly du langage complet NP avec une infinité de chaînes exclues . Selon cette réponse, sous certaines hypothèses cryptographiques naturelles, pour chaque problème co-NP-complet, il existe un sous-ensemble infini d'instances telles que l'appartenance à est un temps polynomial, et le problème de décision limité à est trivial (réponse toujours non).$\Phi$$\Phi$$\Phi$

Cela peut être officialisé en déclarant qu'aucun ensemble co-NP-complet n'est immunisé contre le P. Il est également connu (toujours sous des hypothèses cryptographiques) qu'aucun ensemble NP-complet n'est immunisé contre le P. Il existe donc un autre sous-ensemble infini tel que l'appartenance à est testable en temps polynomial et le problème de décision limité à toujours la réponse oui. Voir par exemple Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, doi: 10.1137 / S009753970444421X .$\Phi'$$\Phi'$$\Phi'$

Une première observation est qu'avoir exactement ce que vous demandez serait une preuve que car cela impliquerait que l'ensemble de toutes les instances ne peut pas être résolu en temps polynomial.$P \neq NP$

Cependant, et je pense que c'est ce que vous vouliez dire, nous pouvons jouer un peu avec ce que nous entendons par «résolu en temps polynomial». Si nous entendons par là tous les sous-ensembles infinis d'instances dont l'appartenance est dans P sont N P -complet, alors la réponse est non par le théorème de Mahaney ( http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute -to-mahaney.html ). Ce théorème stipule qu'aucun problème NP-complet peut être clairsemée à moins que P = N P . Maintenant, en prenant le sous-ensemble d'instances { 0 i ∣ i ∈ N } , nous avons un sous-ensemble clairsemé d'instances pour lequel l'appartenance à l'essai est$\phi$$P$$NP$$P = NP$$\{0^i \mid i \in \mathbb{N}\}$ qui ne peut pas être N P - complet sauf si P = N P par le théorème de Mahaney.$P$$NP$$P = NP$