Problemas que são NP-completos sob reduções aleatórias ou de P / poli.

Em esta questão , que parecem ter identificado um problema natural que é NP-completo sob reduções randomizados, mas possivelmente não sob reduções determinísticos (embora isto depende de qual suposições não comprovadas na teoria dos números são verdadeiras). Existem outros problemas desse tipo conhecidos? Existem problemas naturais que são NP-completos sob reduções de P / poli, mas não são conhecidos por reduções de P?

cc.complexity-theory np-hardness big-list randomness reductions Peter Shor
fonte

Única SAT é

-Hard sob redução randomizado.

N P

$NP$

Mohammad Al-Turkistany

Não vejo por que o Unique SAT não deve contar como resposta (mesmo que não fosse exatamente isso que eu estava procurando). Eu acho que isso conta como um problema natural.

Peter Shor

Eu só queria acrescentar que o menor problema vetorial para LLL sob a norma

para reduções aleatórias (artigo de Ajtai aqui ) é NP-Hard. Até onde eu sei, não é conhecido por ser NP-Hard sob reduções não aleatórias, portanto não atende aos seus critérios, mas achei que deveria ser mencionado de qualquer maneira.

L_{2}

$L_2$

user834

@ Josué: Em alguns problemas completos do NP relacionados a quebra-cabeças (como o Sudoku), a exclusividade de uma solução é uma suposição natural. Eu acho que isso torna o SAT com no máximo uma solução (eu prefiro chamá-lo de SAT inequívoco) mais natural do que parece à primeira vista.

Tsuyoshi Ito

Por que todo mundo está escrevendo respostas nos comentários? : P

Hsien-Chih Chang,

Respostas:

Sob redução aleatória com probabilidade (também conhecido comoredutibilidade , na discussão de reduções aleatórias, consulte "Sobre a satisfação única e reduções aleatórias") $\frac{1}{2}$ $\gamma$

Divisibilidade linear
Equações quadráticas diofantinas binárias

são NP-completos, mas o mesmo não é conhecido para reduções determinísticas (tanto quanto eu sei, para discussões um pouco desatualizadas dessa situação, veja aqui ). redutibilidade foi introduzida no artigo " Redutibilidade, aleatoriedade e intratibilidade ", de Leonard Adleman e Kenneth Manders (também foram propostas provas para os problemas acima). $\gamma$

Existem outros exemplos em " Um catálogo de classes de complexidade ", mas não verifiquei o que se sabe sobre a completude de NP sob reduções determinísticas.

Oleksandr Bondarenko
fonte

Conforme sugerido por Peter, converti meu comentário em uma resposta.

Valente-Vazirani teorema indica que se original sab , em seguida, . Para provar seu teorema eles mostraram que o problema promessa Único SAT é -Hard sob reduções randomizados. $\in P$ $NP=RP$ $NP$

[1] Valiant, Leslie; Vazirani, Vijay. "NP é tão fácil quanto detectar soluções únicas", Theoretical Computer Science, 47: 85–93

Mohammad Al-Turkistany
fonte

Conforme sugerido por Peter, converti meu comentário em uma resposta:

$L_2$ $NP$

user834
fonte