As provas de NP são limitadas ao comprimento polinômio?

Question

.

Na teoria da complexidade computacional, NP (tempo polinomial não interminista) é uma classe complexidade usada para classificar problemas de decisão.NP é o conjunto de problemas de decisão para os quais as instâncias de problemas, onde a resposta é "sim", tem provas verificáveis no tempo polinomial por uma máquina de Turing determinística.

As provas de um problema de decisão NP são verificadas em tempo polinomial.

Isso implica que as provas estão a mais comprimento polinomial?

Bem, você tem que ler toda a entrada. Se a entrada for maior que polinômio, então o tempo é maior que polinômio. "

O problema da decisão "é o primeiro bit da entrada A 0?"pode ser resolvido em tempo e espaço constante - sem ler toda a entrada.

Portanto, talvez algum problema NP tenha provas de candidato que são mais longas que o comprimento polinomial, mas verificadas no tempo polinomial.

Answer 1

.

O problema da decisão "é o primeiro bit da entrada A 0?"pode ser resolvido em tempo e espaço constante - sem ler toda a entrada.

Dado que uma cabeça de máquina de Turing se move para a direita uma etapa de cada vez, uma cabeça de máquina de Turing só pode ler uma quantidade polinômica da prova no tempo polinomial.

Enquanto você pode definir provas para exceder um comprimento polinômico, apenas um prefixo polinomial da prova pode ser lido no tempo polinômio, assumindo que a cabeça inicia na célula 0 e pode mover-se no máximo de uma célula para a direita em uma unidade de tempo.

Answer 2

Uma prova de instância "sim" significa fornecer uma solução.Fornecer uma solução está fornecendo uma entrada válida.Por definição, pode ser verificado em tempo e espaço polinômio relativamente à entrada, ou então, não é um problema no NP.

Não se sabe se todas as provas de instâncias "não" são verificáveis em tempo e espaço polinomial (a diferença entre NP e CO-NP).

Para responder a pergunta precisamente, a prova de uma instância "sim" é o valor de entrada.Você não pode dizer que a entrada tem o comprimento polinômio porque o polinômio é usado ao comparar com o tamanho da entrada.Portanto, a questão é sem sentido por causa da palavra 'polinomial'.Se você realmente quer um polinômio em algum lugar, o tamanho da prova relativamente à entrada pode ser definido como uma função linear f (x)= AX + B onde A= 1 e B= 0, que pode ser simplificado para f (x)= x porque o tamanho da entrada é igual a si mesmo.