Estou lutando para entender a relação entre NP-Intermediário e NP-Completo. Eu sei que se P! = NP baseado no Teorema de Ladner, existe uma classe de idiomas em NP, mas não em P ou em NP-Complete. Todo problema no NP pode ser reduzido a um problema NP-Complete, no entanto, não vi exemplos para reduzir um problema suspeito de NPI (como fatoração de número inteiro) em um problema NP-Complete. Alguém conhece algum exemplo dessa ou de outra redução de NPI-> NPC?
np-complete
reductions
factoring
Nathan Jordan
fonte
fonte
Respostas:
Por exemplo, há uma redução clássica pura de fatoração para SAT, que também é uma fonte de instâncias SAT "difíceis" presumidas. Basicamente, utiliza-se idéias de EE para multiplicação binária codificada no circuito SAT. Pense na multiplicação binária como uma adição de uma série de multiplicandos deslocados à esquerda, cada um "mascarado" (ANDed) pelos bits de um multiplicador. As adições podem ser realizadas por um circuito de adição binária, que é uma série de somadores completos.
Um graduado talentoso poderia criar esse algoritmo. Não sei onde foi proposto ou implementado pela primeira vez na literatura. Eu estaria interessado em ouvir qualquer referência.
Veja, por exemplo, Satisfazer isto: uma tentativa de resolver a fatoração primária usando solventes de satisfação de Stefan Schoenmackers e Anna Cavender, que detalha isso. Além disso, o desafio do DIMACS SAT a partir do final dos anos 90 teve instâncias de fatoração que foram geradas por alguns pesquisadores, mas possivelmente o algoritmo não foi escrito separadamente em um artigo durante essa época.
fonte
Apenas para ficar absolutamente claro, a fatoração de número inteiro não é conhecida como intermediária de NP, apenas suspeita-se que seja baseada na falta de prova de completude de NP ou algoritmo de tempo polinomial (apesar de muito trabalho colocado em ambos). Não conheço nenhum problema natural (ou seja, não construído por Ladner para a prova) que seja definitivamente NP intermediário se P e NP forem diferentes.
Ok, depois desse aviso, o isomorfismo gráfico é outro candidato provável a um problema intermediário natural de NP. Há uma simples redução de tempo polinomial para isomorfismo de subgráfico - basta deixar os gráficos iguais! O isomorfismo de gráfico é apenas o caso especial do isomorfismo de subgráfico, em que os dois gráficos têm o mesmo tamanho. O toque final é que o isomorfismo do subgráfico é NP-completo.
Além disso, sempre há, obviamente, a redução não tão informativa prometida pelo Teorema de Cook-Levin , sabíamos que qualquer problema intermediário de NP tem uma Máquina de Turing não determinística no tempo polinomial que decide e podemos convertê-la em uma instância do SAT (basta criar a TM!).
fonte