Intuição para a classe UP

A classe UP é definida como tal:

A classe de problemas de decisão solucionáveis por uma máquina NP tal que

Se a resposta for 'sim', exatamente um caminho de computação será aceito.

Se a resposta for 'não', todos os caminhos de computação serão rejeitados.

Estou tentando desenvolver intuição para essa definição.

Pode-se dizer que os problemas de UP são problemas com soluções únicas (por exemplo, fatoração primária)?

Isso parece próximo da verdade para mim; mas não posso deixar de pensar que isso significaria, uma vez que UP contém P e está contido em NP, que, no caso de P = NPconseguirmos isso P = UP = NP, todos os problemas também NPtêm soluções únicas, o que parece ser algo comprovadamente não verdadeiro: P != NPpor reductio ad absurdum. Espero que não haja muitas conjecturas e oscilações neste parágrafo para o seu gosto.

cc.complexity-theory complexity-classes valya
fonte

\cap

$\cap$

hm, então isso significa que existe um algoritmo para uma máquina de Turing não determinística, que não é "tenta de maneira não determinística todas as soluções" (pensei que essa é a ideia no coração da equivalência das definições de NP para n.-d. e d. Tm), mas algo mais sofisticado, sempre levando ao resultado único de muitas possíveis ... Isso está certo? Existe outra maneira de declarar isso, por exemplo, usando apenas a ideia de um T determinístico (pode-se definir NP usando apenas ele)?

valya

A intuição de testemunha única está correta, mas deve ser usada com cuidado, pois não significa que todo NTM para ele tenha uma execução única.

Shaull 11/11

Eu amo essa pergunta! Eu tinha exatamente a mesma confusão, mas não via a maneira inteligente de traduzir essa confusão em uma prova simples de que P! = NP. Bem feito!

Vincent Vincent

Mas a sua pergunta do seu último comentário já foi respondida na página da Wikipedia para a classe UP

Vincent

Respostas:

$\mathsf{NP}$ outro tipo de solução que funciona igualmente bem é a atribuição de uma orientação para cada aresta (criando caminhos direcionados de no máximo o número necessário de vértices). Esses dois tipos de soluções podem ser verificados em tempo polinomial, mas por algoritmos diferentes, e também possuem propriedades combinatórias diferentes. Por exemplo, para uma instância de problema típica, o número de atribuições de cores de vértices será diferente do número de orientações de arestas. Muitas pesquisas sobre a aceleração de algoritmos exponenciais para problemas do tipo NP podem ser interpretadas como encontrando uma nova família de soluções para o mesmo problema que tem menos possibilidades de verificação.

$\mathsf{P}$ $\mathsf{NP}$ $\mathsf{UP}$ $\mathsf{P}\subset\mathsf{UP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}=\mathsf{UP}$ . Portanto, não há contradição entre o fato de a solução de cadeia vazia ser única e o fato de que algum outro tipo de solução para o mesmo problema não é exclusivo.

David Eppstein
fonte

U P = N P

$UP=NP$

[a, b]

$[a,b]$

a, b \sim N^{\frac{1}{4}}

$a,b\sim N^{\frac{1}{4}}$

a < b

$a<b$

Novamente, você está assumindo incorretamente que a solução pode ser apenas o fator que você está procurando. Pode haver outras maneiras de resolver o mesmo problema (ou seja, obter uma resposta sim ou não para o N dado) que não consistem em um fator. E se P = NP, a cadeia vazia atende aos requisitos técnicos de uma solução NP - você pode verificá-la em tempo polinomial - e de fato não é um fator, mas é uma solução para o mesmo problema.

21413 David Eppstein

Esta resposta é absolutamente brilhante, pois nos ensina ainda mais do que é solicitado!

Vincent Vincent

$\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{NPMV}$ $\mathsf{NP}$

$\mathsf{NPSV}$ $\mathsf{NPMV}$

$\mathsf{NP}$ $\mathsf{NPMV}$ $\mathsf{NPSV}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{UP}$ $\mathsf{NP} = \mathsf{UP}$ $L \in \mathsf{NP}$ $\mathsf{UP}$ $L$ $\mathsf{NP}$ $L$

Joshua Grochow
fonte