Existem problemas completos de NP sem heurística?

18

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 )ΦΦxΦxPNP

Phylliida
fonte
Veja essa surpreendente conjectura , que é significativamente mais plausível do que parece sua afirmação, pelas razões explicadas pelo artigo.

Respostas:

16

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) .ΦΦΦ

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 .ΦΦΦ

David Eppstein
fonte
Isso é muito legal, obrigado :). Para completar, essas suposições são: existem geradores pseudo-aleatórios e existe uma via permutações seguras
Phylliida
@ Phlliida: Observe que aqueles que estão usando alguma definição teórica da complexidade para "gerador pseudo-aleatório", em vez de uma definição criptográfica usual.
0

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.PNP

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 ii N } , temos um subconjunto esparso infinito de instâncias para as quais a associação de teste estáϕPNPP=NP{0iiN} que não pode ser N P -completo a menos que P = N P pelo Teorema de Mahaney.PNPP=NP

holf
fonte
Ah desculpe, o que eu quis dizer é que eles não podem ser resolvidos em tempo polinomial assumindo , você está certo de que isso é muito importantePNP
Phylliida