Regra geral para saber se um problema pode estar completo como NP

Esta pergunta foi inspirada por um comentário no StackOverflow .

Além de conhecer os problemas NP-completos do livro Garey Johnson e muitos outros; existe uma regra de ouro para saber se um problema se parece com um NP-completo?

Não estou procurando algo rigoroso, mas algo que funcione na maioria dos casos.

Claro, toda vez que temos que provar que um problema é NP-completo, ou uma ligeira variante de um NP-completo; mas antes de correr para a prova, seria ótimo ter certa confiança no resultado positivo da prova.

Esta é minha abordagem pessoal para determinar se um problema (ou seja, um idioma ) é NP completo ou não. Se ambas as condições forem verificadas:$L$

• Eu sinto que o teste se uma instância está em L implica que eu preciso verificar todas as combinações de algum tipo$I$$L$
• e que não há como dividir essa combinação em duas menores

$L$

$S$$S$$S_1$$S_2$$S_1$$S_2$

$A$$C$$B$$A$$B$$B$$C$

Francamente, essa abordagem é muito básica: tento encontrar um algoritmo (polinomial) para o problema em questão. Se não consigo encontrar um, o problema se torna "difícil" no meu ponto de vista. A seguir, vem todo o raciocínio de NP-completeness: poderei codificar um problema de NP-complete existente para este? (E como isso geralmente é muito mais difícil, tento mais uma vez encontrar um algoritmo polinomial ..)

Eu suspeito que essa é a maneira usual de pensar. No entanto, permanece bastante difícil de aplicar em problemas desconhecidos. Pessoalmente, lembro-me de ter sido surpreendido por um dos primeiros exemplos de completude de PN que me disseram: o problema da camarilha . Parecia tão simples de verificar! Então, suponho que a experiência tenha muito a ver com isso. Também a intuição pode ser inútil às vezes. Lembro-me de ter dito várias vezes dois problemas quase idênticos, mas um estava em P e o outro com uma pequena variação era NP-completo.

Ainda estou para encontrar um bom exemplo (preciso de ajuda aqui), mas isso é como o problema pós-correspondência : esse é um problema indecidível, mas algumas variantes são decidíveis.

Outra perspectiva sobre a dureza do problema vem da comunidade de jogos e quebra-cabeças, onde a regra geral é que 'os problemas são os mais difíceis possíveis' (e as exceções vêm de estruturas ocultas no problema - o exemplo de Massimo comentários é um bom exemplo disso); o truque é entender o quão difícil pode ser um problema:

• $n$
• Os quebra-cabeças que envolvem uma sequência de movimentos dentro de um espaço de estado delimitado estão no PSPACE (uma vez que a 'árvore de movimento' geralmente pode ser explorada da maneira mais profunda em profundidade, necessitando apenas de armazenamento para um número polinomial de configurações) e tende a ser completo no PSPACE; um exemplo clássico disso é a hora do rush.
• Jogos com profundidade polinomialmente limitada também estão no PSPACE; isso usa a caracterização de PSPACE como APTIME, uma vez que a caracterização min-max usual de estratégias imita perfeitamente uma máquina de Turing alternada com sua caracterização como 'existe um movimento para o jogador A, de modo que, para cada resposta movida pelo jogador B, exista uma resposta mover para o jogador A de modo que ... ', etc. Eles também tendem a ser completos no PSPACE; Os jogos Hex e Tic-Tac-Toe generalizados são exemplos disso.
• Jogos sem limite na profundidade da árvore, mas jogados em um espaço delimitado (polinomialmente) estão em EXPTIME, pois existem exponencialmente muitas posições totais e todo o gráfico pode ser construído e explorado em tempo polinomial no número de posições (e, portanto, exponencial em geral) ; esses jogos geralmente são EXPTIME-complete. Xadrez, Damas e Go, todos se enquadram nessa categoria.