¿Hay algún problema completo de NP libre de heurística?

¿Hay algún problema completo de NP sin un subconjunto infinito de instancias tal manera que la membresía en se pueda decidir en tiempo polinómico, y para todos , se pueda resolver en tiempo polinómico? (Suponiendo )Φ x ∈ Φ x P ≠ N $\Phi$$\Phi$$x \in \Phi$$x$$P \neq NP$

Vea la respuesta de Josh Grochow al superconjunto Poly time del lenguaje completo NP con infinitas cadenas excluidas de él . Según esa respuesta, bajo algunos supuestos criptográficos naturales, para cada problema co-NP-completo hay un subconjunto infinito de de instancias tales que la membresía en es tiempo polinómico, y el problema de decisión restringido a es trivial (respuesta siempre no).Φ $\Phi$$\Phi$$\Phi$

Esto se puede formalizar al afirmar que ningún conjunto co-NP-completo es P-inmune. También se sabe (nuevamente bajo suposiciones criptográficas) que ningún conjunto completo de NP es inmune a P. Entonces, hay otro subconjunto infinito tal que la membresía en es comprobable en tiempo polinómico y el problema de decisión restringido a siempre tiene respuesta sí. Véase, por ejemplo, Glasser et al., "Properties of NP-Complete Sets", SICOMP 2006, doi: 10.1137 / S009753970444421X .Φ ′ Φ $\Phi'$$\Phi'$$\Phi'$

Una primera observación es que tener exactamente lo que pides sería una prueba de que ya que implicaría que el conjunto de todas las instancias no se puede resolver en tiempo polinómico.$P \neq NP$

Sin embargo, y creo que eso es lo que quisiste decir, podemos jugar un poco con lo que queremos decir con "resuelto en tiempo polinómico". Si entendemos por que todos los subconjuntos infinitos de instancias cuyos miembros son en P son N P -Complete, entonces la respuesta es no, por el Teorema de Mahaney ( http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute -to-mahaney.html ). Este teorema establece que no hay problema NP-completo puede ser escasa a menos que P = N P . Ahora, tomando el subconjunto de instancias { 0 i ∣ i ∈ N } , tenemos un subconjunto de instancias disperso infinito para el cual se encuentra la membresía de prueba$\phi$$P$$NP$$P = NP$$\{0^i \mid i \in \mathbb{N}\}$ que no puede ser N P -completo a menos que P = N P por el teorema de Mahaney.$P$$NP$$P = NP$