Existem problemas completos de NP sem heurística?

Há algum problema NP completo com nenhum subconjunto infinito de instâncias tal que a adesão em Φ pode ser decidida em tempo polinomial, e para todo x ∈ Φ , x pode ser resolvido em tempo polinomial? (Assumindo P ≠ N P )$\Phi$$\Phi$$x \in \Phi$$x$$P \neq NP$

Veja a resposta de Josh Grochow ao superconjunto do tempo poli da linguagem completa NP com infinitas cordas excluídas . De acordo com essa resposta, sob algumas suposições criptográficas naturais, para cada problema co-NP-completo há um subconjunto infinito de instâncias tais que a adesão em Φ é tempo polinomial, e o problema de decisão restrita a Φ é trivial (resposta sempre não) .$\Phi$$\Phi$$\Phi$

Isso pode ser formalizado afirmando que nenhum conjunto co-NP completo é imune a P. Também é sabido (novamente sob premissas criptográficas) que nenhum conjunto completo de NP é imune a P. Portanto, não há outro subconjunto infinito tal que a adesão em Φ ' é testável de tempo polinomial e o problema de decisão restrita a Φ ' tem sempre sim resposta. Veja, por exemplo, Glasser et al., "Propriedades dos conjuntos completos NP", SICOMP 2006, doi: 10.1137 / S009753970444421X .$\Phi'$$\Phi'$$\Phi'$

Uma primeira observação é que ter exatamente o que você pergunta seria uma prova de que , pois implicaria que o conjunto de todas as instâncias não pode ser resolvido no tempo polinomial.$P \neq NP$

No entanto, e acho que foi isso que você quis dizer, podemos brincar um pouco com o que queremos dizer com "resolvido em tempo polinomial". Se queremos dizer com isso todos os subconjuntos infinitos de instâncias cuja adesão está em P são N P -completo, então a resposta é não por Teorema de Mahaney ( http://blog.computationalcomplexity.org/2007/06/sparse-sets-tribute -to-mahaney.html ). Este teorema indica que nenhum problema NP-completo pode ser escasso, a menos que P = N P . Agora, considerando o subconjunto de instâncias { 0 i ∣ i ∈ N } , temos um subconjunto esparso infinito de instâncias para as quais a associação de teste está$\phi$$P$$NP$$P = NP$$\{0^i \mid i \in \mathbb{N}\}$ que não pode ser N P -completo a menos que P = N P pelo Teorema de Mahaney.$P$$NP$$P = NP$