Existem problemas fáceis de calcular, mas difíceis de verificar?

Supondo que P NP, os problemas completos de NP sejam "difíceis de resolver, mas têm respostas fáceis de verificar". Faz algum sentido considerar o contrário, ou seja, problemas para os quais é fácil calcular uma resposta correta, mas difícil de verificar uma solução arbitrária? $\neq$

Eu acho que esse problema implicaria:

Exponencialmente muitas respostas "corretas" para qualquer entrada, porque, caso contrário, a verificação poderia ser realizada simplesmente computando todas as respostas corretas.
Algumas respostas "corretas" são fáceis de calcular, mas outras são difíceis de encontrar.

complexity-theory rphv
fonte

Eu duvido. Se uma resposta é fácil de calcular, a escolha do certificado é fácil: forneça a resposta pretendida com o problema e "verifique" a resposta resolvendo o problema e verificando se a resposta pretendida é realmente a resposta.

Patrick87

@ Patrick87 - Eu acho que resolvi isso na questão. E uma função com valores múltiplos que associa um conjunto de valores a uma entrada ? Suponha que , e é fácil escolher um elemento de , mas, dado , é difícil determinar se .

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

Rphv 19/09/12

@ Patrick87 O solucionador pode ser determinístico e gerar apenas uma de todas as respostas existentes. Você precisa de uma maneira eficiente de verificar se duas soluções são equivalentes. A equivalência em um conjunto pode ser mais difícil do que resolver um problema nele?

Raphael

Na verdade, eu perdi essa parte, desculpe. Ainda assim, estou inclinado a duvidar da premissa. Pensarei um pouco mais e voltarei se tiver pensamentos mais pertinentes.

precisa saber é o seguinte

Um certificado geralmente significa que existe uma maneira fácil de reconstruir uma prova; portanto, por definição, se você fornecer um certificado, a verificação é fácil. Uma solução sem certificado pode ser difícil.

Gilles 'SO- stop be evil'

Respostas:

Se você está bem com problemas artificiais, pode fazer muitos deles. Aqui estão alguns:

Dado um número inteiro positivo n em unário, responda uma fórmula 3CNF satisfatória em n variáveis booleanas.
É fácil fornecer uma fórmula 3CNF satisfatória, mas decidir se uma dada fórmula 3CNF é satisfatória ou não é 3SAT, um problema bem conhecido de NP-completo.
Não há entrada. Basta atender uma máquina de Turing que para (quando é executada com uma fita de entrada vazia).
É fácil dar uma dessas máquinas de Turing, mas se uma determinada máquina de Turing pára ou não é indecidível.

Adicionado : a propósito, não acho que o que você escreveu no último parágrafo contenha:

Penso que esse problema implicaria exponencialmente muitas respostas "corretas" para qualquer entrada, porque, caso contrário, a verificação poderia ser realizada simplesmente computando todas as respostas corretas.

Se o problema tiver uma solução, verificar a resposta não é mais difícil do que calcular a solução correta. No entanto, se o problema tiver uma solução fácil e outra difícil, você não poderá calcular todas as soluções com eficiência. Aqui está um desses problemas (que é muito artificial):

Dada uma máquina de Turing M , responda a uma das seguintes afirmações verdadeiras: “ M pára na fita de entrada vazia”, “ M não pára na fita de entrada vazia” e “ M é uma máquina de Turing”.
É fácil fornecer uma solução : você sempre pode escolher “ M é uma máquina de Turing”. No entanto, se uma determinada resposta está correta ou não é indecidível. Observe que nesse problema, existem apenas duas soluções para cada instância.

Tsuyoshi Ito
fonte

Existe uma maneira razoável de definir formalmente o que significa esses problemas serem "artificiais"? (Por "razoável", quero dizer algo com o qual podemos concordar amplamente, como dizer que uma definição de "computável" captura nossa intuição do que deveria significar.)

Gilles 'SO- deixa de ser mau', em

@ Gilles: Não, acho que não. Chamei esses problemas de "artificiais" porque é muito improvável que alguém os encontre primeiro e depois descubra que é fácil dar uma resposta e difícil decidir a correção de um determinado candidato. Mas essa "artificialidade" não é de forma alguma uma noção rigorosa.

Tsuyoshi Ito

@ Tsuyoshi Ito - Obrigado por sua resposta clara. Editei o último parágrafo para refletir sua visão.

Rphv 20/09/12

Embora a resposta de Tsuyoshi Ito cubra a resposta "principal", havia duas notas mais sutis que eu gostaria de acrescentar.

Mesmo quando a solução é difícil de verificar, ainda é fácil verificar a solução com uma sequência curta de provas. Ou seja, ao estender um pouco a solução com informações extras, ela se torna facilmente verificável; a verificação está sempre em NP. Uma maneira de ver isso é que o agente que calcula uma solução pode registrar todos os bits aleatórios que eles usam e, em seguida, o verificador pode usar a mesma sequência aleatória para executar a mesma computação. (O provador deve usar bits aleatórios, caso contrário, eles sempre emitem a mesma resposta, e o verificador sempre pode verificar facilmente calculando uma resposta pelo mesmo método.)
Para computadores quânticos, essa é uma pergunta muito aberta. Para computadores clássicos, o verificador sempre pode fazer algo como simular o provador e verificar se ele recebe a mesma resposta. É perfeitamente possível que, para algum problema complicado, exista um algoritmo quântico que produz uma distribuição uniforme em todas as soluções (exponencialmente numerosas), difíceis de verificar. Você não pode executar o teste novamente, porque provavelmente obterá uma resposta diferente a cada vez.

Como exemplo de um tipo semelhante de problema, o problema da Deutsch-Jozsa sofre um pouco com isso. Se um oráculo não é uma função equilibrada, um computador quântico pode determinar rapidamente que esse é o caso, mas não há prova curta que permita que um computador clássico verifique isso. (Este é apenas um problema "semelhante" porque ele ainda pode ser verificado por outro computador quântico, e a verificação também ocorre no BPP clássico, mesmo que não esteja em P.)

Alex Meiburg
fonte