No deterministas polinomio de tiempo del algoritmo frente a certificado/verificador para mostrar la pertenencia NP

Question

En este papel (https://arxiv.org/pdf/1706.06708.pdf), los autores demuestran que la forma óptima de resolver el $n imes n imes n$ El Cubo de Rubik es un NP-completo el problema.En el proceso, se debe demostrar que la decisión pertinente problema pertenece a NP (sección 2.5 en la página 6).Para ello, se describe un algoritmo que nondeterministically resuelve el Cubo en el polinomio de tiempo.A mí me parece que esto es más esfuerzo que el necesario.

En particular, la decisión pertinente problema es el siguiente:El Cubo de Rubik problema tiene como entrada una permutación $t$ y un valor $k$.El objetivo es decidir si $t$ puede ser resuelto en $k$ o menos se mueve.Así que en lugar de construir una polinomial no determinista en tiempo algoritmo de solución, ellos simplemente tienen que dar un certificado de que un "sí" la decisión es sólo una lista de más de $k$ se mueve y se compruebe que el control de este es el polinomio de tiempo.

Así que mis preguntas son las siguientes.Son las dos definiciones, a continuación, en realidad equivalente?

1. NP es la complejidad de la clase de problemas de decisión que se pueden resolver por una máquina de Turing no determinista en tiempo polinomio.
2. NP es la complejidad de la clase de problemas de decisión para que una solución puede ser confirmado en el polinomio de tiempo (determinista)?

Y si son equivalentes, ¿por qué los autores de las páginas de papel, elija el más difícil el método (o estoy equivocado acerca de este supuesto)?

---

Tenga en cuenta que estoy publicando esta pregunta en varios StackExchange sitios web, ya no estoy seguro de que es mejor ajuste.Si es inapropiado aquí, me voy feliz de eliminar.Del mismo modo, voy a enlazar a una buena solución en otro sitio si se responde no.

Answer 1

El certificado que propone podría no ser polinomial en el tamaño de la entrada.

El tamaño de entrada del problema es $ o (n ^ 3 + \ log k) $ , mientras que su certificado tiene tamaño $ \ Omega (k \ log n) $ .Esto no es polinomial, por ejemplo, por $ k= 2 ^ n $ .

Su certificado funcionaría si lo configura, por ejemplo, a una lista vacía cuando $ k=^ 2 \ frac {n ^ 2} {\ log n}) $ , y modifique el verificador para simplemente verificar si la configuración de entrada del cubo es solvable para cualquier valor de este tipo de $ k $ (por lo tanto, ignorando el certificado).