Problemas NP-completos que admitem um algoritmo eficiente sob a promessa de uma solução única

Eu estava lendo recentemente um artigo muito bom por Valiant e Vazirani que mostra que se , então não pode haver um algoritmo eficiente para resolver SAT mesmo sob a promessa de que ela é ou insatisfatível ou tem uma solução única. Assim, mostrando que o SAT não admite um algoritmo eficiente, mesmo sob a promessa de haver no máximo uma solução. $\mathbf{NP \neq RP}$

Por meio de uma redução parcimoniosa (uma redução que preserva o número de soluções), é fácil ver que a maioria dos problemas completos de NP (eu poderia pensar) também não admite um algoritmo eficiente, mesmo sob a promessa de haver no máximo uma solução (a menos que ). Os exemplos seriam VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING. $\mathbf{NP = RP}$

Por isso, fiquei pensando se havia algum problema de NP-completo que soubesse admitir um algoritmo de politempo sob uma promessa de exclusividade.

np-hardness np-complete unique-solution promise-problems Diabo
fonte

Essa não é uma resposta muito boa, mas há muitos problemas de NP-completos cujas instâncias sempre têm zero ou mais de uma solução. Considere a coloração do gráfico 3, por exemplo; as soluções vêm em grupos de 6, pois você sempre pode permutar as cores. Qualquer problema desse tipo tem um algoritmo de tempo polinomial sob a promessa de no máximo uma solução. Em particular, se houver no máximo uma coloração 3, não poderá haver nenhuma e, portanto, o algoritmo poderá simplesmente rejeitar.

Mikhail Rudoy

O problema do ciclo hamiltoniano admite um algoritmo de tempo mais rápido (mas ainda exponencial) sob a promessa de uniqness. Não está a responder diretamente sua pergunta, porque não é polinomial, mas pelo menos este é um problema com tbehaviour differen seguida, SAT

ivmihajlin

Como no comentário de Mikhail Rudoy, testar a existência de um ciclo hamiltoniano em gráficos tridimensionais é trivial com uma suposição de exclusividade. Cada borda participa de um número par de ciclos hamiltonianos, portanto nunca pode haver exatamente um.

David Eppstein

Problemas NP-completos que admitem um algoritmo eficiente sob a promessa de uma solução única

Respostas: