Existe uma tarefa solucionável no tempo polinomial, mas não verificável no tempo polinomial?

Um colega meu e eu acabamos de fazer algumas anotações de um de nossos professores. As notas indicam que existem tarefas que são possíveis de resolver em tempo polinomial (estão na classe de PF), mas NÃO são verificáveis em tempo polinomial (NÃO são da classe de NPF).

Para elaborar sobre essas classes: Nós obtemos alguma entrada X e produzimos alguma saída Y tal que (X, Y) estejam em relação R representando nossa tarefa. Se for possível obter Y para X em tempo polinomial, a tarefa pertence à classe de PF. Se for possível verificar o certificado de comprimento polinomial Z que comprove que uma tupla (X, Y) está em relação R em tempo polinomial, a tarefa pertence à classe de NPF.

Não estamos falando de problemas de decisão, onde a resposta é simplesmente SIM ou NÃO (mais formalmente se alguma string pertencer a algum idioma). Para problemas de decisão, parece que PF é um subconjunto adequado de PFN. No entanto, para outras tarefas, pode ser diferente.

Você conhece uma tarefa que pode ser resolvida no tempo polinomial, mas não verificada no tempo polinomial?

complexity-theory np Drozi
fonte

Talvez eu entenda mal, mas por que o seguinte não é um algoritmo de verificação em tempo polinomial? Dado

(x, y)

$(x,y)$ , calcule a função

f (x)

$f(x)$ , usando o algoritmo de tempo polinomial, e retorne "correto" se

f (x) = y

$f(x)=y$ . É possível que você tenha interpretado mal ou o professor tenha falhado errado e pretenda dizer que há problemas verificáveis no tempo polinomial, mas não solucionáveis no tempo polinomial?

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen "dizendo que existem problemas verificáveis no tempo polinomial, mas não solucionáveis no tempo polinomial?" [ref. necessário]

T. Verron 8/16

@ T.Verron Haha, sim, eu também ficaria muito feliz de ver a prova do professor para essa afirmação;)

Lieuwe Vinkhuijzen

Respostas:

Isso só é possível se houver muitas saídas admissíveis para uma determinada entrada. Ou seja, quando a relação não é uma função porque viola a singularidade. $R$

Por exemplo, considere este problema:

Dado (representado em unário) e uma TM , produza outra TM modo que e (onde representa a codificação (número de Gödel) de em uma número natural) $n \in \mathbb{N}$ $M$ $N$ $L(M)=L(N)$ $\# N > n$ $\# N$ $N$

Resolver isso é trivial: continue adicionando alguns estados redundantes ao TM , possivelmente com algumas transições fictícias entre eles, até que sua codificação exceda . Esta é uma aplicação repetida básica do Lemma Padding nas TMs. Isso exigirá preenchimentos, cada um dos quais pode adicionar um estado; portanto, isso pode ser feito em tempo polinomial. $M$ $n$ $n$

Por outro lado, dado é indecidible para verificar se é um resultado correcto para as entradas de . De fato, marcar é indecidível (aplique o teorema de Rice), e a restrição apenas descarta finitos muitos s desses. Como removemos uma quantidade finita de elementos de um problema indecidível, ainda temos um problema indecidível. $n,M,N$ $N$ $n,M$ $L(M)=L(N)$ $\#N > n$ $N$

Você também pode substituir a propriedade indecidível para obter variações ainda computáveis, mas NP rígidas / completas. Por exemplo, dado que (em unário), é trivial calcular um gráfico com uma classe dentro. Porém, dado , é difícil verificar se existe um -ique. $L(M)=L(N)$ $n$ $G$ $n$ $n,G$ $n$

chi
fonte

Esperava que esse não fosse o caso. Ótima resposta!

Filip Haglund

Isso não responde à pergunta. O PO solicitou especificamente um problema não verificável no sentido usual, onde, além da entrada e da suposta resposta, obtemos um certificado

que certifica a exatidão da resposta. No seu caso, o certificado são os bits usados para gerar não-deterministicamente a nova máquina de Turing equivalente. Dado

, é fácil verificar se

dá a máquina

. Sem

, a questão é se é fácil gerar instâncias rígidas de linguagens (NPC), o que é verdade apenas no Minicrypt e na Cryptomania.

z

$z$

M, N

$M, N$

z

$z$

z

$z$

M

$M$

z

$z$

Lieuwe Vinkhuijzen

@chi Nem todos os pares

podem ser certificados, mas o conjunto de pares

gerado pelo seu algoritmo pode ser certificado. O certificado é a transcrição do seu algoritmo que produz

(por exemplo, "comece com

, adicione este estado e adicione esta transição, depois ... e pronto,

!"). Em geral, se

é um algoritmo não determinístico que, dado

, sempre calcula um

admissível , uma transcrição de um caminho de computação de

é um certificado de que um determinado

é admissível.

M, N

$M, N$

M, N

$M, N$

N

$N$

M

$M$

M

$M$

N

$N$

T

$T$

x

$x$

y

$y$

T (x)

$T(x)$

y

$y$

Lieuwe Vinkhuijzen

@chi Há uma ligeira nuance na pergunta: Para uma relação arbitrária

, é possível que nem todos admissível

são certificados, e você dar um exemplo elegante. No entanto, a pergunta não pergunta se existem relações admissíveis, mas não-certificáveis (a resposta é sim , pelo seu exemplo); em vez disso, pergunta se podemos ter um algoritmo que produz resultados admissíveis e não-certificáveis. A resposta, aqui, deve ser não , por causa do argumento acima.

R

$R$

y

$y$

Lieuwe Vinkhuijzen

$NP\subsetneq P$

Isso é apenas uma elaboração da primeira frase da resposta de @ chi, pois não achei óbvio.

A idéia é que, se você tiver um algoritmo que encontre a resposta para algum problema no tempo polinomial, existem duas possibilidades:

Você já provou (matematicamente) que a saída do algoritmo é uma solução para o problema; nesse caso, as próprias etapas do algoritmo formam a prova de correção.
Você tem um algoritmo diferente para verificar se a saída é realmente uma solução; nesse caso, você deve estar executando esse algoritmo (caso contrário, estaria no caso 1), o que implica que você está fazendo isso em tempo polinomial.

Portanto, não pode haver esse problema.

Mehrdad
fonte

Eu não entendo # 2. O que implica que o algoritmo diferente seja executado em tempo polinomial?

Albert Hendriks

@AlbertHendriks: se o verificador não fosse executado no tempo polinomial, o solucionador original não poderia afirmar ter encontrado uma solução correta no tempo polinomial, porque ele precisa executar o verificador para garantir que sua solução esteja correta.

26518 Mehrdad