Tengo un problema de decisión con certificados de tamaño de $2^n$ bits, ¿cómo verificaría mi problema de decisión de manera eficiente si está en $NP$?

Question

Problema de decisión:Es $2^k$ + $M$ un primo?

Las entradas para ambos $k$ y $M$ son solo números enteros.La solución es la suma de $2^k$+$M$. (Utilice AKS para decidir la prima)

Las potencias de 2 tienen aproximadamente $2^n$ dígitos.Considerar $2^k$ dónde $k$ = 100000.Compara la cantidad de dígitos en $k$ a la cantidad de dígitos en su solución!

Pregunta

Viendo que el certificado del problema de decisión puede ser $2^n$ tamaño, ¿cómo verificaría el problema de decisión en tiempo polinómico, considerando que puedo mirar los estados de transición como un certificado en sí mismo?

En otras palabras, ¿cómo sería un verificador de tiempo polinomial para este problema de decisión?

Answer 1

Un problema de decisión tiene una respuesta de sí / no, por lo que no puede tener "tamaño exponencial".Usted está preguntando por los problemas de búsqueda, aquellos pueden tener un tamaño exponencial.Y sí, si el tamaño de la solución (escrito en un formato adecuadamente compacto, es decir) es exponencial en el tamaño del problema original, es claramente imposible incluso anotar la respuesta en el tiempo polinomial.

En cualquier caso, P y NP se aplican estrictamente solo a los problemas de decisión.Pero eche un vistazo a Belare's "La decisión vs Buscar" para unrelación entre ambos.