Eu tenho um problema de decisão com us $2^n$ bits de tamanho certificados, como posso verificar o meu problema de decisão de forma eficiente, se ele está em $NP$?

Question

Problema De Decisão:É $2^k$ + $M$ um prime?

As entradas para ambos $K$ e $M$ são apenas inteiros.A solução é a soma de $2^k$+$M$. (Use AKS para decidir prime)

As potências de 2 aproximadamente $2^n$ dígitos.Considere $2^k$ onde $K$ = 100000.Comparar a quantidade de dígitos $K$ para a quantidade de dígitos é a solução!

Pergunta

Vendo que o problema de decisão do certificado pode ser $2^n$ porte, como eu poderia verificar o problema de decisão em tempo polinomial, considerando que eu só posso olhar para os estados de transição como um certificado em si?

Em outras palavras, o que seria um tempo polinomial verificador de parecer para este problema de decisão?

Answer 1

Um problema de decisão tem um sim/não responde, então ele não pode ter "exponencial tamanho".Você está perguntando sobre problemas de pesquisa, aqueles que podem, certamente, ter exponencial tamanho.E sim, se o tamanho da solução (escrito em algum devidamente formato compacto, o que é) é exponencial no tamanho do problema original, é claro que é impossível até mesmo escrever a resposta em tempo polinomial.

Em qualquer caso, P e NP estritamente aplicam apenas aos problemas de decisão.Mas dê uma olhada no Belare do "Decisão vs Pesquisa" para uma relação entre ambos.