¿Son las pruebas NP limitadas a la longitud polinomial?

Question

En la teoría de la complejidad computacional, NP (tiempo polinomial no determinista) es una clase de complejidad utilizada para clasificar los problemas de decisión.NP es el conjunto de problemas de decisión para los cuales las instancias problemáticas, donde la respuesta es "Sí", tiene pruebas verificables en el tiempo polinomial por una máquina de Turing determinista.

Las pruebas de un problema de decisión de NP se verifican en tiempo polinomial.

¿Esto implica que las pruebas son en la mayoría de la longitud polinomial?

"Bueno, tiene que leer la entrada completa. Si la entrada es más larga que el polinomio, entonces el tiempo es mayor que el polinomio".

El problema de la decisión "es el primer bit de la entrada A 0?"se puede resolver en tiempo y espacio constante, sin leer toda la entrada.

Por lo tanto, tal vez algún problema NP tenga pruebas candidatas que sean más largas que la longitud polinomial, pero se verifican en el tiempo polinomial.

Answer 1

El problema de la decisión "es el primer bit de la entrada A 0?"se puede resolver en tiempo y espacio constante, sin leer toda la entrada.

Dado que la cabeza de la máquina de Turing se mueve hacia abajo un paso a la vez, un cabezal de la máquina de Turing solo puede leer una cantidad polinomial de la prueba en el tiempo polinomial.

Si bien podría definir pruebas para exceder una longitud polinomial, solo se podría leer un prefijo polinomial de la prueba en el tiempo polinomial, suponiendo que la cabeza se inicie en la celda 0 y pueda moverse a una célula máxima a la derecha en una unidad de una sola vez.

Answer 2

Una prueba de "sí" significa proporcionar una solución.Proporcionar una solución es proporcionar una entrada válida.Por definición, se puede verificar en el tiempo y el espacio polinomial relativamente a la entrada, o de lo contrario, no es un problema en NP.

Se desconoce si todas las pruebas de instancias "no" son verificables en el tiempo y el espacio polinomial (la diferencia entre NP y CO-NP).

Para responder a la pregunta con precisión, la prueba de una instancia de "sí" es el valor de entrada.No puede decir que la entrada tiene longitud polinomial porque se usa polinomio cuando se compara con el tamaño de entrada.Por lo tanto, la pregunta no tiene sentido debido a la palabra 'polinomio'.Si realmente desea un polinomio en algún lugar, el tamaño de la prueba relativamente a la entrada puede definirse como una función lineal f (x)= AX + B donde A= 1 y B= 0, que se puede simplificar a f (x)= x porque el tamaño de la entrada es igual a sí mismo.