Como o problema do vendedor ambulante é verificável em tempo polinomial?

21

Então eu entendo a ideia de que o problema de decisão é definido como

Existe um caminho P tal que o custo seja menor que C?

e você pode facilmente verificar se isso é verdade, verificando o caminho que você recebe.

No entanto, e se não houver um caminho que atenda a esse critério? Como você verificaria a resposta do "não" sem resolver o melhor problema de TSP do caminho e descobrir o melhor caminho tem um custo pior que o C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
fonte
Pessoalmente, eu só tinha ouvido falar que a classe NP significava verificação de tempo poli, mas nunca havia visto a restrição de que isso significa apenas verificar respostas de "sim, aqui está a solução". Parece intuitivo imaginar que você deve ser capaz de verificar qualquer solução no tempo poli.
Wjmccann

Respostas:

36

NP é a classe de problemas em que você pode verificar instâncias "yes". Não há garantia de que você possa verificar instâncias "não".

A classe de problemas em que você pode verificar instâncias "não" em tempo polinomial é co-NP . Qualquer idioma no co-NP é o complemento de algum idioma no NP e vice-versa. Exemplos incluem coisas como não-3-colourability. O problema que você descreve: "Não existe um caminho TSP com comprimento no máximo  ?" também está em co-NP : se você desmarcar a negação dupla, uma instância "não" para esse problema é uma instância "yes" para o TSP e podemos verificar as ocorrências em tempo polinomial.C

Existem alguns problemas, como fatoração de número inteiro e qualquer problema em  P , que sabemos estar em NP e co-NP . (Obrigado a user21820 por apontar isso.)

Não se sabe se NP e co-NP são o mesmo conjunto de problemas. Se forem iguais, podemos verificar as instâncias "yes" e "no" do TSP. Se eles são diferentes, então P NP≠ , já que sabemos que P co-P= (porque podemos apenas negar a resposta de uma máquina determinística, dando a resposta para o problema do complemento) .

David Richerby
fonte
4
Vale ressaltar que conhecemos alguns problemas que estão no NP e no coNP, mas que não sabemos se eles estão no P ou não, como a fatoração de número inteiro.
precisa saber é o seguinte
@ user21820 A fatoração de número inteiro não é um problema de decisão. A primazia é um problema de decisão e, durante anos, era conhecido por ambos os grupos, NP e co-NP . Finalmente, foi mostrado ser em P bem. Eu não sei se ainda há problemas conhecidos para estar em ambos NP e co-NP sem ter se mostrado em P .
kasperd
4
@kasperd: É um fato bem conhecido que a fatoração inteira, quando transformada em um problema de decisão (n tem um fator primo menor que m?), está em NP e coNP (ambas as instâncias sim / não podem ser verificadas em tempo polinomial via o teste de primalidade da AKS, dada a fatoração primária como certificado), mas ainda não foi mostrado em P.
#
1
@ user21820 Existem formas muito mais simples e rápidas de verificar uma fatoração do que o AKS.
kasperd
@ Kasperd: Eu ficaria curioso para aqui isso. Para verificar uma fatoração, você precisaria, por exemplo, dos fatores primos e, para cada fator primo, uma prova de que ele é primo.
precisa saber é o seguinte
2

"Como é possível verificar o problema do vendedor ambulante em tempo polinomial?"

Ou na maneira como você descreve, ou não se sabe que seja assim.

"No entanto, e se não houver um caminho que atenda a esse critério?"

Nesse caso, para todas as máquinas NP para o problema de decisão, a máquina retornará não para todos os certificados-candidatos.

"Como você verificaria a resposta de" não "sem resolver o melhor problema de TSP do caminho e descobrir o melhor caminho tem um custo pior que o C?"

Bem, pode-se receber uma prova interativa de que não existem tais caminhos .

O problema que você descreve, TSP, não é conhecido como coNP ; portanto, não é conhecido como um modo "NP-like" de verificar se esse caminho não existe.

Juho
fonte