Para mostrar a dureza NP de um problema, é necessário escolher um problema NP-difícil conhecido e encontrar uma redução polinomial do problema conhecido para o problema em questão. Teoricamente, qualquer problema NP-difícil pode ser usado para a redução, mas, na prática, alguns dos problemas são mais facilmente reduzidos do que outros.
Por exemplo, o 3-SAT é geralmente uma escolha melhor para construir uma redução do que o SAT porque o primeiro é mais restrito que o último, a 3-partição é geralmente uma escolha mais fácil do que a embalagem de lixeira, ...
Uma maneira de encontrar esses problemas "bons" para a redução é fazer uma análise estatística das reduções existentes. Por exemplo, pode-se moldar todos os pares de from -> toreduções do livro Computadores e Intratabilidade: Um Guia para a Teoria da Completude NP
(ou outros recursos) e desenhar um histograma dos problemas do fromconjunto. Em seguida, podemos descobrir quais problemas são mais comumente usados para reduções.
Eu me pergunto se essa análise estatística faz algum sentido. Essa pesquisa já foi realizada ou não? Caso contrário, qual é o seu palpite sobre os problemas mais usados para reduções.
A razão pela qual estou fazendo essa pergunta é que já fiz algumas provas de dureza NP, mas quase todas elas se baseiam na redução do mesmo problema (3 partições). Estou procurando outras opções para usar em minhas provas.
fonte
Respostas:
Não sei se existe uma maneira de fazer isso, mas minha pequena experiência pessoal funciona da seguinte maneira.
Eu tento fornecer um algoritmo de tempo polinomial para um problema. Nessas tentativas, geralmente vejo que existem algumas versões restritas do problema que são solucionáveis em tempo polinomial. Também vou entender qual parte do meu algoritmo estava agitando à mão para o problema original. Posso comparar esses dois casos (a diferença entre as versões restritas e a geral também faz parte de um algoritmo difícil de melhorar). Ao comparar esses dois casos, geralmente é possível adivinhar como é o gargalo do problema. Para que possamos encontrar um problema difícil relacionado. Normalmente, fornecer um algoritmo para um problema é um trabalho árduo e precisa de bons conhecimentos sobre um problema. Depois de obtermos esse conhecimento sobre o problema, podemos ter muitas idéias diferentes para resolver o problema em diferentes cenários (não apenas resultados de dureza).
PS: Se sua prova se baseia em um problema específico, acho que é porque esse problema está muito próximo do seu trabalho, então não se culpe.
fonte