Pode-se determinar se a linguagem L está em NP?

15

Dada uma linguagem L definida por uma máquina de Turing que a decide, é possível determinar por algoritmo se L está no NP?

txwikinger
fonte
Retagged à teoria da complexidade. Não tenho certeza do que isso tem a ver com a NP-Completeness.
Aryabhata
11
FWIW, apesar dos votos no site da proposta, acho que essa questão está mais dentro do escopo do que a questão da fatoração justamente porque a questão da fatoração seria abordada na maioria dos cursos de introdução à complexidade, mas essa nem sequer é abordada em muitos cursos de pós-graduação cursos de complexidade.
Joshua Grochow 17/08/10
11
Isso não é abordado em cursos introdutórios sobre computabilidade como uma aplicação típica do teorema de Rice?
Moritz
3
Moritz - embora a resposta sim / não a esta pergunta esteja coberta pelo Teorema de Rice, veja minha resposta abaixo para obter resultados mais interessantes. Talvez, txwikinger, você deva alterar a pergunta para "Qual é a complexidade do conjunto {i: L (M_i) está em NP}?")?
Joshua Grochow 17/08/10
Vou responder a resposta de Joshua aqui. A resposta pode ser óbvia quando o idioma é especificado por uma Máquina de Turing, mas a resposta é a mesma (e talvez não tão aparente) se permitirmos que o idioma seja especificado em algum formato arbitrário.
Anand Kulkarni

Respostas:

24

Não. Primeiro, pelo Teorema de Rice, essa é uma propriedade das TMs que depende apenas do idioma que elas computam, portanto não pode ser computável.

Mas, mais do que isso, sabe-se que o conjunto de índices de (ou seja, o conjunto de TMs que computam idiomas em N P ) é Σ 0 3 - completo ( Σ 0 3 na hierarquia aritmética da computabilidade, não o hierarquia polinomial).NPNPΣ30 0Σ30 0

Perguntas como essa foram investigadas pela primeira vez por Hajek . Para mais, consulte, por exemplo, este artigo de Ken Regan.

Mais algumas ótimas pepitas do jornal de Hajek:

  • O conjunto de índices de é Σ 0 3 - completo.PΣ30 0
  • é Π 0 2 -completo{Eu:Peu(MEu)NPeu(MEu)}Π20 0
  • Existe uma máquina de Turing total (pára em todas as entradas) modo que P L i = N P L i, mas a declaração " P L i = N P L i " é independente (onde L i = L ( M i ) ) . Da mesma forma para relativizações onde P N P .MEuPeuEu=NPeuEuPeuEu=NPeuEueuEu=eu(MEu)PNP
Joshua Grochow
fonte
11
Aqui, a pergunta parece ser um problema de decisão de promessa (o idioma fornecido promete ser decidido por uma TM, não apenas reconhecida), em oposição a um problema de decisão total. O Teorema de Rice ainda será aplicável aqui então? Lembre-se de que a prova do Teorema de Rice emprega a indecidibilidade da parada, portanto a indecidibilidade é essencial lá.
Zeyu 17/08/10
2
Na pergunta feita, a linguagem L foi "dada por uma máquina que a decide". Então foi realmente: dada uma máquina de Turing M, é possível determinar se L (M) está em NP. Se a linguagem L não fosse especificada por uma TM, mas meramente fornecida como um subconjunto dos números naturais, o que significaria decidir algoritmicamente se L estiver em NP? Em particular, como podemos pensar em L como sendo introduzido em um algoritmo quando L em si não é fornecido por uma descrição finita?
Joshua Grochow 17/08/10
11
Sim eu conheço. Porém, no Teorema de Rice, é possível que a MT não decida um idioma, ou seja, não calcule uma função total.
Zeyu 17/08/10
2
É uma heurística geral que, dada uma propriedade semântica das máquinas de Turing, como "M define uma linguagem NP", deve-se primeiro tentar expressar essa propriedade na lógica de primeira ordem. Isso coloca a propriedade em um nível da Hierarquia Aritmética; a heurística é que a propriedade geralmente está completa para esse nível da hierarquia. Gostaria de perguntar se existem contra-exemplos notáveis ​​nessa heurística.
Andy Drucker
2
Escalando para a Hierarquia Polinomial, é menos provável que as coisas se comportem tão bem. Por exemplo, considere a propriedade "C é um circuito booleano de tamanho mínimo (para a função que calcula)". Esse problema é difícil para o NP e pode ser colocado na hierarquia polinomial, mas está aberto se estiver completo para o nível em que reside naturalmente. (esses resultados são conhecidos por algumas classes restritas de circuitos, por exemplo, DNFs; veja a pesquisa em duas partes "Completude in the Hierarchy Polynomial" por Schaefer e Umans.)
Andy Drucker
5

A resposta para sua pergunta literal é não, como Joshua Grochow apontou.

No entanto, como Holger afirmou, é possível verificar em tempo linear se a máquina de Turing não-determinística (NTM) "se controla" e pára após n ^ k etapas para alguma constante k, através de alguma maneira padrão de simular um relógio (como o código abaixo). Frequentemente, quando um artigo ou livro sugere (incorretamente) que é possível determinar se um MNT é um tempo polinomial, é isso que eles realmente querem dizer. Talvez seja por isso que você fez a pergunta? (Eu tive a mesma pergunta quando aprendi a teoria da complexidade e vi em algum lugar a afirmação de que é possível verificar se uma MT é poli-tempo.) A verdadeira questão é por que alguém pode querer fazer isso, o que discuto abaixo depois de explicar como .

Existem muitas maneiras de adicionar esse recurso de relógio. Por exemplo, imagine na entrada x de comprimento n, executando alternadamente uma instrução do "algoritmo primário" sendo sincronizada e, em seguida, uma instrução do algoritmo a seguir, que termina em (algo próximo a) n ^ k etapas:

para i_1 = 1 en
  para i_2 = 1 en
...
        para i_k = 1 en
          no-op;
Retorna;

Se o código acima retornar antes que o algoritmo primário pare, interrompa todo o cálculo (por exemplo, com rejeição).

O algoritmo que decide se um NTM é dessa forma, se interpretado como uma tentativa de um algoritmo para decidir se sua entrada é um NTM com tempo poligonal, relatará alguns negativos negativos: é garantido que alguns NTMs parem no tempo polinomial, embora eles não alternam a execução de uma instrução de um algoritmo com uma instrução de um relógio como o código acima (portanto, seria rejeitado apesar de ser poli-horário).

Mas não há falsos positivos. Se um NTM passa no teste, ele definitivamente pára no tempo polinomial, portanto define alguma linguagem NP. No entanto, talvez o comportamento de seu algoritmo primário subjacente seja alterado, se o relógio às vezes se esgotar antes que o algoritmo primário pare, fazendo com que a computação seja rejeitada, mesmo que o algoritmo primário possa ter aceitado se tiver tempo suficiente para terminar. Portanto, a linguagem decidida pode ser diferente da linguagem do algoritmo primário. Mas, e isso é fundamental, se o algoritmo primário em execução for de fato um algoritmo de tempo polinomial executando no tempo p (n) e se a constante k no relógio for grande o suficiente para que n ^ k> p (n), então o algoritmo primário sempre parará antes que o relógio acabe. Nesse caso, a resposta do algoritmo primário não é alterada; portanto, o algoritmo primário e o NTM com clock simulando-o, portanto, decidem a mesma linguagem NP.

Por que isso é importante? Isso significa que é possível "enumerar todas as linguagens NP" (que, como eu disse, na literatura é muitas vezes imprecisa, declarada como "decidir se um determinado NTM é poli-tempo" ou "enumerar todos os NTMs do poli-tempo"). Mais precisamente, é possível enumerar uma lista infinita de M_1 M_2, ..., do NTM, com as propriedades que

  1. Cada M_k é executado em tempo polinomial (por exemplo, anexando um relógio ^ k-time a M_k), portanto, decide alguma linguagem NP e
  2. Cada idioma NP é o idioma decidido por alguns M_i na lista.

O que não acontece é que todos os NTM em tempo polinomial estão na lista. Mas cada linguagem NP tem um número infinito de NTMs representando-o. Portanto, é garantido que cada idioma NP tenha pelo menos alguns de seus NTMs representativos na lista, especificamente todos os NTMs em um índice k suficientemente grande que n ^ k exceda o tempo de execução de M_k.

Isso é útil para fazer truques como diagonalização, que exigem enumerar algoritmicamente essas listas infinitas (ou ilimitadas) de todas as linguagens NP. E, é claro, toda essa discussão se aplica a muitos outros tipos de máquinas, além dos NTMs de politempo, como as TMs determinísticas de politempo.

Dave Doty
fonte
3

p(n)

Holger
fonte
2
Isso só funciona se for uma TM não-determinística com clock . Se eu apenas der uma MT com clock (mesmo que seja executado em tempo exponencial), ainda é indecidível se o idioma que ele decide é ou não em NP. No entanto, se N_1, N_2, ... é uma enumeração de TMs com relógios exponenciais, o conjunto {i: L (N_i) está em NP} provavelmente não está mais completo com Sigma_3, pois você já está garantido que os N_i estão total, mas certamente ainda não é computável.
Joshua Grochow