Dada uma linguagem L definida por uma máquina de Turing que a decide, é possível determinar por algoritmo se L está no NP?
cc.complexity-theory
computability
turing-machines
txwikinger
fonte
fonte
Respostas:
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).NP NP Σ0 03 Σ0 03
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:
fonte
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:
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
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.
fonte
fonte