Todo problema NP-difícil é computável?

19

É necessário que um problema difícil de NP seja computável?

Acho que não, mas não tenho certeza.

Kevin Meier
fonte

Respostas:

15

N, uma N PNP problema -Hard não precisa de ser calculável. A definição é bastante completa: um problema GL é N PNP -Hard se o problema de ter uma solução de tempo poli implica qualquer problema em N PNP tem uma solução de tempo de poli (isto é, uma redução de GL existe para cada problema em N PNP .).

Problemas incontestáveis ​​são, então, vacuamente difíceis: suponha que possamos resolver um em tempo polinomial. Em seguida, usamos a prova de que é incontestável derivar que é computável e incontestável, uma contradição. Deste falsidade, podemos derivar qualquer coisa, ou seja, que existe um algoritmo de tempo polinomial para qualquer N PNP problema que estamos olhando.

Por exemplo, considerar o problema da paragem HH . Podemos reduzir qualquer linguagem N P de A para H da seguinte maneira, assumindo que tenhamos um verificador polytime f ( s , c ) que verifica se c é um certificado para s A :NPAHf(s,c)csA

  • Dados dados ss
  • Construção (mas não execute) Máquina de Turing MM que leva entrada xx tenta cada certificado cc e paradas se cc é um certificado verificando que s AsA .
  • Retornar H ( M , x ) (ou seja, retornar verdadeiro se M parar na entrada x )H(M,x)Mx

Assim, com uma única chamada para um algoritmo de tempo poli resolver o Deter problema, podemos resolver qualquer N P problema em tempo polinomial.NP

Essa redução não é útil, porque tudo o que faz é dizer se "se falso, então alguma coisa". Já sabemos que não existe um algoritmo polytime para problemas incontestáveis.

jmite
fonte
7
"A definição está razoavelmente completa", mas não é o que segue essa citação na sua resposta.
Eu tenho uma pergunta sobre isso. Posso imaginar uma função que resolve o problema de parada para o maior conjunto de programas possível sob algumas restrições apropriadas, mas posso imaginar que essa função ainda não seja computável (no sentido de que nunca a encontraríamos, mesmo com uma quantidade infinita de tempo) . No entanto, se de alguma forma se tem a solução para isso, não é mesmo claro para mim que ele deve resolver todos os problemas NP-difíceis necessariamente. Portanto, ou a lógica nesta resposta não segue (significando indecidível! = Incontestável), ou meu raciocínio é falho (provável). Então, qual é a falha?
Mehrdad
12
A maior parte desta resposta está incorreta, incluindo sua definição de NP rígido: o problema A é NP rígido se, "para cada problema NP B, houver uma redução no tempo poli de B para A." Isso não é a mesma coisa que "se A for poli-tempo, então P = NP". (O último é uma conseqüência do primeiro, mas não vice-versa.) Em particular, há quase certamente problemas não computáveis ​​que também falham em ser NP difíceis. Ainda não elaborei os detalhes, mas o problema de pertencer a um conjunto suficientemente genérico (no sentido de forçar) deve funcionar. O conjunto de interrupção, especificamente, é NP-difícil, no entanto, por sua redução.
7
Pense em uma redução de politempo de A para B assim: é um programa que é executado em tempo polinomial, mas tem a capacidade especial de consultar, em uma única etapa, um oráculo que responde a instâncias do problema B. Independentemente de saber se existe um algoritmo poli-tempo para B, ou mesmo se B é computável, ainda faz sentido fazer a seguinte pergunta: supondo que o oráculo responda corretamente às perguntas feitas (em uma única etapa), o programa em questão executar em tempo polinomial e resolver corretamente instâncias do problema A?
2
@ MikeHaskel Sua analogia com o oracle só é precisa se, após consultar o oracle, o programa precisar parar com a mesma resposta que o oracle. Caso contrário, o co-SAT é reduzido para SAT: consulte o oráculo e negue. Em algumas noções de redução, por exemplo, redução de Turing, isso seria aceitável, mas na redução padrão do tempo poli, ou mesmo em muitas reduções, não é.
Chi
16

Parece haver alguma confusão considerável nessa comunidade em relação a essa questão. Darei uma resposta detalhada na esperança de limpar a água e iluminar a relação entre computabilidade e dureza NP.

Primeiro, acredito que ser claro e explícito sobre as várias definições envolvidas resolverá muita confusão.

Uma string é uma sequência finita de caracteres de algum alfabeto finito fixo.

Um problema de decisão é um conjunto de strings. (Esse conjunto geralmente é infinito.) Pense no problema de decisão como cadeias de teste para alguma propriedade: as cadeias com a propriedade estão no conjunto e as cadeias sem a propriedade não.

Suponha que temos dois problemas de decisão, A e B . Digamos que A seja redutível em tempo polinomial para B se houver algum polinômio p ( x ) e algoritmo algum algoritmo M, de modo que, para todas as strings s ,ABABp(x)Ms

  • Se você fornecer M com entrada s , M será interrompido em menos de p ( | s | ) etapas (onde | s | é o comprimento da sequência s ) e gera uma sequência M ( s ) .MsMp(|s|)|s|sM(s)
  • s é em A , se e apenas se H ( s ) é em B .sAM(s)B

Um problema de decisão B é NP-hard se, por cada NP problema de decisão A , A é redutível em tempo polinomial para B .BAAB

Um problema de decisão é computável se houver um algoritmo M , que, para todas as strings s ,Ms

  • Se você fornecer a M as entradas s , M interromperá e emitirá "yes" ou "no".MsM
  • A saída é "yes" se s estiver em A e "no" caso contrário.sA

Com as definições acima, podemos esclarecer imediatamente o que acho que pode ser a principal raiz da sua pergunta: nada nas definições de problema de decisão, reduções ou dureza de NP exige que os problemas de decisão sejam computáveis. As definições fazem todo sentido, pensando nos problemas de decisão como conjuntos arbitrários de strings, e esses conjuntos podem ser muito desagradáveis.


Isso deixa duas perguntas sobre a mesa:

  1. As definições deixam em aberto a possibilidade de que funções não computáveis ​​possam ser difíceis para NP. Existem, na verdade , funções NP-hard não computáveis?
  2. Existe uma intuição de que dizer que um problema é difícil para o NP está dizendo que é difícil de resolver. Dizer que não é computável é como dizer que é "realmente difícil" de resolver. Então, todos os problemas não computáveis ​​são difíceis de processar?

A pergunta 1 é mais fácil de responder. Existem duas maneiras particularmente importantes de encontrar problemas de decisão não computáveis ​​que são difíceis para o NP. O primeiro é o problema da parada: o problema da parada, H , tem a propriedade de que cada computável problema de decisão é redutível em tempo polinomial para H . Como os problemas de NP são computáveis, todos os problemas de NP são reduzidos em tempo polinomial para H , então H é NP.HHHH

A outra maneira importante de criar um problema NP-hard não computável é observar que podemos combinar qualquer problema NP-hard conhecido com qualquer problema não-computável conhecido. Seja A NP rígido e B não computável. Forme o problema de decisão A B da seguinte maneira: A B contém as seqüências de caracteres do formato "0, seguidas por uma sequência de caracteres em A " e as do formulário "1, seguidas de uma sequência de caracteres em B ". A B é NP-difícil porque podemos transformar qualquer redução (de qualquer problema) em A em uma redução em A BABABABABABAAB: basta ajustar o algoritmo para gerar um "0" extra na frente da string de saída. A B não é computável, pois a computação de A B requer a decisão de quais cadeias que começam com "1" estão no conjunto; isso é impossível, pois B não é computável.ABABB


A questão 2 é consideravelmente mais complicada, mas, de fato, existem problemas de decisão não computáveis ​​que não são difíceis de NP (assumindo P NP). A boa resposta de Yuval constrói esse problema de decisão explicitamente. (Para todos os teóricos da computabilidade na sala, qualquer "Cohen Π 0 1 -generic" irá fazer o truque, também.) Eu vou quebrar porque a intuição de que "problemas NP-difíceis são difíceis problemas, não computáveis são mais difíceis " está errado.Π01

A dureza NP e a não-computabilidade dizem que um problema é "difícil" em um sentido muito geral, mas são muito diferentes e não devem ser agrupados como o mesmo tipo de fenômeno. Especificamente, a dureza NP é uma propriedade "positiva": um problema NP rígido A é difícil no sentido de que, dado o acesso a uma folha de dicas para A , você pode resolver uma classe difícil de problemasAA . Por outro lado, a não computabilidade é uma propriedade "negativa": um problema não computável A difícil no sentido de que você não pode resolver A com uma determinada classe de recursosAA .

("Forçar", a propósito, é a técnica usada para produzir o "Cohen Co 0 1 genérico" que eu mencionei. Para ser muito vago, forçar é uma maneira geral de produzir coisas que são "genéricas", pois possuem sem propriedades positivas e todas as propriedades negativas. É por isso que o forçar pode produzir diretamente um problema que não é computável nem difícil de NP.)Π01

Comunidade
fonte
2
Você não pode construir uma linguagem indecidível que não seja NP-difícil por diagonalização? Diagonalize contra todos os decisores e todas as reduções de polytime do SAT.
Yuval Filmus
1
@YuvalFilmus Isso provavelmente funciona, sim. Eu acho que escrever os detalhes de por que a diagonalização em relação às reduções de politempo do SAT é uma quantidade possível é similar em sabor a mostrar que o trabalho forçado, no entanto, não pensei nisso nesses termos.
1
@YuvalFilmus Também adicionei o esclarecimento agora que você deve assumir P NP: houve definitivamente uma etapa em minha prova que dizia "resolva um problema no NP, mas não no P."
1
@aelguindy Não sei ao certo qual é o método mais acessível para provar isso. Mencionei a técnica de forçar , que é muito geral e poderosa. Aprendi com as pessoas, não com os livros didáticos, por isso não conheço pessoalmente uma grande referência em forçar. Como Yuval apontou, no entanto, forçar provavelmente é um exagero: algum argumento mais direto envolvendo diagonalização provavelmente funciona. "Conjuntos e graus recursivamente enumeráveis" de Soare é um livro que cobre muito desse estilo de argumento, se você quiser se familiarizar com ele. Novamente, a maior parte é provavelmente um exagero. ...
1
@aelguindy Além disso, se você pensar no conjunto de problemas de decisão como um espaço topológico, provavelmente poderá massagear o teorema da Categoria Baire para produzir uma prova. Esse teorema está intimamente relacionado ao forçar, mas é mais antigo e direto.
11

Não. NP-Hard significa que é tão difícil ou mais difícil que os problemas mais difíceis de NP. Intuitivamente, ser desconectável tornará muito mais difícil que o NP.

Wikipedia:

Existem problemas de decisão que são difíceis de NP, mas não completos, por exemplo, o problema de parada.

Todo mundo sabe que não é computável

Limão destrutível
fonte
4
Observe que, enquanto alguns problemas não computáveis ​​(como o problema de parada) são difíceis de NP, isso não significa que todos os problemas não computáveis ​​são difíceis de NP. Veja meus comentários sobre a resposta de jmite. A dureza NP é uma propriedade positiva: diz que as respostas para o seu problema podem ajudar a resolver problemas de NP. Ser NP-difícil implica que o problema é, até certo ponto, difícil. Nem todos os problemas difíceis são difíceis de NP.
@MikeHaskel: Possuindo a solução para o problema da paragem reduz todos os problemas de P * dificuldade do problema da paragem ..
Joshua
1
@ Josué: Isso não faz sentido. É como um fragmento de uma não prova. O que você quer dizer com um problema para ter um número finito de bits em sua solução e por que você acha que isso se aplica a todos os problemas incontestáveis? O que você quer dizer com "P * pára"? O que é o resto de "reduzir via enésima parte de ..."?
User2357112 suporta Monica
1
@ Josué: Parece que a questão principal é que você está assumindo que todo problema corresponde a uma máquina de Turing. Nem todo problema corresponde a uma máquina de Turing. Não há problem()função que possamos chamar.
User2357112 suporta Monica
1
Você provavelmente deve mover este para conversar ou algo
Destrutível Lemon
9

Para completar, vamos provar o seguinte teorema:

Existe uma linguagem incontestável que não é difícil para NP se e somente se P NP.

Se P = NP, qualquer idioma não trivial (que difere de , { 0 , 1 } ) é NP-difícil (exercício) e, em particular, qualquer linguagem não-confiável é NP-difícil.,{0,1}

Agora suponha que P NP. Deixe- T i haver alguma enumeração de todas as máquinas de Turing. Construiremos o idioma necessário L em etapas. Em cada etapa, vamos manter a { 0 , 1 , ? } coloração de { 0 , 1 } que também denotamos por L ; aqui 0 significa que decidimos que a string não está em L , 1 significa que decidimos que a string está em L e ?TiL{0,1,?}{0,1}L0L1L?significa que ainda não decidimos. Todas as cordas, com exceção de finitas, serão coloridas ? .?

Na etapa 2 i , pensamos em T i como uma máquina que seja aceita sua entrada, rejeita, ou nunca pára. Se T i nem sempre parar, em seguida, nós não fazemos nada. Se T i sempre pára então encontramos uma string x tal que L ( x ) = ? e defina L ( x ) : = 0 se T i ( x ) aceita e L ( x ) : = 1 se T2iTiTiTixL(x)=?L(x):=0Ti(x)L(x):=1 i ( x ) rejeita.Ti(x)

No passo 2 i + 1 , pensamos t i como uma máquina de calcular um (possivelmente) função parcial na sua entrada. Se T i não é total, ou se é total, mas não é executado em tempo polinomial, ou se é total, mas seu alcance é finito, não fazemos nada. Se T i é total, é executado em tempo polinomial, e tem alcance infinito, então encontramos uma string x tal que L ( T i ( x ) ) = ? . Se x S A2i+1TiTiTixL(Ti(x))=? T (ou seja, se xxSATxcodifica um CNF satisfatório), então definimos L (x ) : = 0 x ) : = 1 . e, caso contrário, definimos L (L(x):=0L(x):=1

Depois infinitamente muitas etapas, temos um { 0 , 1 , ? } coloração de { 0 ,{0,1,?} 1 } que concluímos em um idioma real de maneira arbitrária.{0,1}

O idioma resultante L não é computável: a etapa 2 i garante que T i não o calcule. Também não é difícil para o NP, mas aqui o raciocínio é um pouco mais delicado. Suponha-se que o t i é uma redução polytime de sab para L . Se o intervalo de T i é finito, então podemos transformar T i em uma máquina polytime decidir SAT, listando a tabela verdade de L na gama de T i . Isso é impossível pela suposição P NP. Assim t i tem uma gama infinita, mas, em seguida, o passo 2 iL2iTiTiLTiTiLTiTi + 1 exclui a redução de SAT para L2i+1L .

Yuval Filmus
fonte
3

Uma linguagem L é NP-difícil se para cada L 'N P temos que L ' é redutível em tempo polinomial para L . O problema de aceitação para máquinas de Turing não determinísticasLLNPLL

ANTM={M,wM is a nondeterministic Turing machine that accepts w}

ANTM={M,wM is a nondeterministic Turing machine that accepts w}

is undecidable and is NP-hard. For consider an LNPLNP. LL is decided by some nondeterministic Turing machine MM with polynomial time complexity. A poly-time reduction ff from LL to ANTMANTM is given by

f(x)=M,x

f(x)=M,x
Hans Hüttel
fonte
3

I think what causes people to think there is no uncomputable NP-hard problem is that they miss the point that NP-hardness is a lower bound on the hardness of a problem, not an upper bound on their hardness like P or NP.

A language L being NP-hard means that it is above language in NP and that is. Now if you understand this what need is to show that there are arbitrary harder problem.

Let A be a language. Consider algorithms augmented with a black-box that they can use to deciding membership in A. Let's denote them by CA. It is easy to see that the halting problem for CA, HaltCA is not in CA.

In computablity theory this is called jump of A and is denoted by A. So A<A strictly. And nothing stops us from repeating this: A<A<A<A<...

Kaveh
fonte