¿Qué problemas se sabe que requieren tiempo superpolinómico o mayor para resolverlos?

Question

Tengo dificultades para encontrar problemas que se sabe que requieren más tiempo que polinomial para resolver (superpolinomial), especialmente en teoría de grafos.

Entonces, ¿qué problemas (o mejor aún, clase de problemas) se ha demostrado que requieren tiempo superpolinomial o más para llegar a una solución definitiva (especialmente en teoría de grafos)?

Para clarificar, estoy apuntando a problemas matemáticamente importantes, como el problema del vendedor viajero, isomorfismo de grafos, problemas de conteo, problemas de decisión y de satisfacción. Hay muchos, muchos ejemplos en P y NP, pero parece más difícil encontrar ejemplos en exptime (es posible que simplemente sea malo buscando en Google :-)).

Answer 1

Wiki da un ejemplo interesante aquí

Considera Sudoku, un juego donde al jugador se le da una cuadrícula parcialmente llena de números e intenta completar la cuadrícula siguiendo ciertas reglas. Dada una cuadrícula de Sudoku incompleta, de cualquier tamaño, ¿hay al menos una solución legal? Cualquier solución propuesta se puede verificar fácilmente, y el tiempo para verificar una solución crece lentamente (polinómicamente) a medida que la cuadrícula se hace más grande. Sin embargo, todos los algoritmos conocidos para encontrar soluciones toman, para ejemplos difíciles, tiempo que crece exponencialmente a medida que la cuadrícula se hace más grande.

Y para EXPTIME, aquí:

En la teoría de la computabilidad, uno de los problemas básicos indecidibles es el problema de detención: decidir si una máquina de Turing determinista (DTM) se detiene. Uno de los problemas EXPTIME-completos más fundamentales es una versión más simple de esto, que pregunta si una DTM se detiene en a lo sumo k pasos. Está en EXPTIME porque una simulación trivial requiere tiempo O(k), y la entrada k se codifica utilizando O(log k) bits lo que causa un número exponencial de simulaciones. Es EXPTIME-completo porque, hablando en términos generales, podemos usarlo para determinar si una máquina que resuelve un problema EXPTIME acepta en un número exponencial de pasos; no usará más

Para Teoría de Grafos, este artículo recientemente demostró ser EXPTIME-completo:

Investigamos la complejidad computacional de decidir si k policías pueden capturar a un ladrón en un grafo G. Goldstein y Reingold (1995) [8] conjecturaron que el problema es EXPTIME-completo cuando tanto G como k son parte de la entrada; probamos esta conjetura.

No estoy seguro de tu habilidad matemática así que simplemente dejaré el artículo de wiki sobre qué son los policías y los ladrones; disculpa si esto es condescendiente (esto es nuevo para mí).