¿Hay algún problema que requiera más tiempo exponencial de resolución (por ejemplo, doble exp.) Pero que pueda verificarse en tiempo polinómico determinista?

Cualquier problema que pueda verificarse en tiempo polinómico determinista es, por definición de NP, en la clase NP. Entonces, esta pregunta es equivalente a la pregunta: “¿Hay algún problema en NP con un cierto límite inferior en el tiempo de ejecución?”

Caso 1: si nos interesan los límites inferiores de tiempo de la forma, existe una constante real ‘a’ positiva de tal manera que el problema no puede resolverse en un tiempo inferior a 2 ^ {an}, entonces un sí a esta pregunta significaría que, no solo “NP no es igual a P”, sino también “NP no es igual a Sub-exponencial”, es decir, ETH es cierto . Por otro lado, un no significaría que ETH es falso . Tenga en cuenta que “P = NP?” Aún permanecería abierto en este caso. Por lo tanto, esta pregunta esencialmente pregunta si ETH es verdadero o no , y una creencia popular es que sí es cierto.

Enlace wiki para ETH “Hipótesis de tiempo exponencial – Wikipedia” y el enlace wiki para la definición de sub-exponencial “Complejidad de tiempo – Wikipedia”.

Caso 2: Si nos preocupan los límites inferiores de tiempo estrictamente mayores que exponenciales , donde exponencial significa 2 ^ (poli (n))), entonces la respuesta de esta pregunta es no , ya que todos los problemas de NP pueden resolverse en tiempo exponencial por bruto -Forzar a través de todos los certificados posibles expresables en longitud polinómica. Debido a la garantía de que el problema es verificable en tiempo polinómico, sabemos que al menos un certificado de longitud polinómica podría verificarlo correctamente.

Caso 3: Este es el caso intermedio que surge porque las funciones de la forma 2 ^ {O (n)} no están en la clase sub-exponencial, ni contienen la clase exponencial por completo. Entonces, si estamos preocupados por los límites inferiores de tiempo de la forma 2 ^ {O (n)}, es decir, el problema no puede resolverse en un tiempo inferior a 2 ^ {O (n)}, entonces ETH ser falso dará un Sí, responde a esta pregunta. Pero, siendo ETH cierto no nos dará ninguna respuesta . Debido a que es posible que todos los problemas de NP no se puedan resolver en un tiempo sub-exponencial sino que se puedan resolver en 2 ^ {O (n)} tiempo, y así no obtenemos una respuesta. Por otro lado, si algún problema en NP requiere al menos 2 ^ {superlineal (n)} tiempo, obtenemos una respuesta afirmativa.

Quizás, pero eso quizás se sienta sobre si P = NP.

Si suponemos que P = NP, entonces no, todos los problemas que pueden verificarse en tiempo polinomial pueden resolverse en tiempo polinómico.

Si P! = NP y si no me equivoco, hay algoritmos que requieren más que un tiempo exponencial para resolver, sin embargo, no puede haber problemas de doble tiempo exponencial NP.

Considera esto. Digamos que tiene un problema de decisión D. Desea encontrar una cadena binaria que satisfaga D que tenga una longitud n. Digamos que D toma O (n ^ 2) tiempo de ejecución, luego pasar cada posible cadena de longitud n a D tomará O (n ^ 2 * 2 ^ n) tiempo de ejecución, que es técnicamente peor que exponencial. Sin embargo, nunca puede ser doble exponencial. Esto se debe a que n ^ m * 2 ^ n = O (2 ^ 2 ^ n) para todos los valores de m. Entonces, si D es polinomial, siempre hay una solución O (n ^ m * 2 ^ n).