Consequências de UP é igual a NP

19

EDIT em 08/02/2011: Depois de encontrar e ler algumas referências, decidi separar a pergunta original em duas. Aqui está a parte referente a UP vs NP. Para a parte das classes sintáticas e semânticas, consulte Benefícios para as classes sintáticas e semânticas .


UP (o tempo polinomial inequívoco, consultewikieo zoológicopara obter referências) é definido como idiomas decididos pelas máquinas NP com uma restrição adicional que

  • Existe no máximo um caminho de computação aceito em qualquer entrada.

As relações precisas entre P vs UP e UP vs NP ainda estão abertas. Sabemos que de pior caso de sentido único funções existe se e somente se PUP , e há oráculos relativos a todas as possibilidades das inclusões PUPNP .

Estou interessado em saber por que UP vs NP é uma questão importante. As pessoas tendem a acreditar (pelo menos na literatura ) que essas duas classes são diferentes, e meu problema é:

Se UP=NP , houve alguma conseqüência "ruim"?

Há um post relacionado no blog de complexidade em 2003. E se meu entendimento estiver correto, o resultado de Hemaspaandra, Naik, Ogiwara e Selman mostra que, se

  • Existe uma linguagem L tal que para cada fórmula satisfatória ϕ existe uma atribuição satisfatória única x com ( ϕ , x ) em L ,NPLϕx(ϕ,x)L

a hierarquia polinomial cai para o segundo nível. Nenhuma implicação desse tipo é conhecida se UP=NP mantiver.

Hsien-Chih Chang 張顯 之
fonte
(1) É fácil ver (quase por definição) que UP e BPP têm problemas completos se "problemas" podem se referir a problemas promissores. Eles não são conhecidos por terem idiomas completos . (2) Não conheço a definição precisa de classes sintáticas. PH é sintático? Ele não tem um problema completo (mesmo com promessa), a menos que a hierarquia polinomial colapse. (3) Não conheço o uso da notação “PromiseUP.” Se NP significa a classe de idiomas reconhecida por uma máquina NP e PromiseUP significa a classe de problemas de promessa reconhecidos por uma máquina UP, então claramente eles não podem ser iguais.
Tsuyoshi Ito
@ Tsuyoshi: Obrigado pelas perguntas. (1) Por problemas, quero dizer idiomas , é minha culpa que não escrevo isso claramente. (2) Definimos classes sintáticas como tendo caracterizações de linguagem foliar em máquinas com tempo poli. O PH é especial, uma vez que não é conhecida a caracterização da linguagem foliar poli-tempo, onde línguas completas naturais são garantidas; mas o PH possui uma caracterização de idioma em folha do espaço de logs . (mais)
Hsien-Chih Chang,
(cont.) (3) Talvez o uso do PromiseUP não esteja correto. Aqui com PromiseUP, quero dizer uma classe de linguagens , de modo que, para instâncias yes, a máquina possui um caminho de aceitação exclusivo, e para nenhuma instância a máquina possui zero ou pelo menos dois caminhos de aceitação.
Hsien-Chih Chang,
Obrigado pela resposta. Quanto a (3), a partir de uma análise superficial do artigo de Hemaspaandra, Naik, Ogihara e Selman, não consigo encontrar uma maneira de declarar o resultado em termos de problemas de decisão. BTW, o link para o papel está quebrado. Aqui está um link para a versão do diário .
Tsuyoshi Ito
2
Apenas para garantir, o PromiseUP é completamente diferente do que você descreveu. Como escrevi, PromiseUP é a versão com problema de promessa do UP; ou seja, é a classe de problemas de promessa que possui uma máquina de Turing M de tempo polinomial não determinístico, de modo que, para as instâncias sim, M possui exatamente um caminho de aceitação e, para as instâncias M , não possui caminhos de aceitação. Embora eu acredite que PromiseUP seja o nome tradicional para esta classe, algumas pessoas (inclusive eu) a escrevem simplesmente como UP.
Tsuyoshi Ito

Respostas:

4

UP=NPSpanP=#PUP=NPSpanP=#P#PSpanP

Uma função está em se houver um transdutor de máquina de Turing tal que, para todos , seja o número de saídas distintas de em entrada .S p a n P N P M x f ( x ) M xf:ΣNSpanPNPMxf(x)Mx

J. Kobler, U. Schoning e J. Toran. Em contagem e aproximação , Acta Informatica, 26: 363-379, 1989.

Mohammad Al-Turkistany
fonte
2
Esta resposta ( cstheory.stackexchange.com/a/20645/495 ) também funciona aqui, pois se então a conjectura separada de pares de é falsa. N PUP=NPNP
Mohammad Al-Turkistany