Consequências de UP é igual a NP

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 .

$\mathsf{UP}$ (o tempo polinomial inequívoco, consultewikieo zoológicopara obter referências) é definido como idiomas decididos pelas $\mathsf{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 $\mathsf{P}$ vs $\mathsf{UP}$ e $\mathsf{UP}$ vs $\mathsf{NP}$ ainda estão abertas. Sabemos que de pior caso de sentido único funções existe se e somente se $\mathsf{P} \neq \mathsf{UP}$ , e há oráculos relativos a todas as possibilidades das inclusões $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$ .

Estou interessado em saber por que $\mathsf{UP}$ vs $\mathsf{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 $\mathsf{UP} = \mathsf{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 tal que para cada fórmula satisfatória existe uma atribuição satisfatória única com em , $\mathsf{NP}$ $L$ $\phi$ $x$ $(\phi,x)$ $L$

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

cc.complexity-theory complexity-classes conditional-results unique-solution 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

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

Consequências de UP é igual a NP

Respostas: