Límites inferiores de complejidad temporal superlineal para cualquier problema natural en NP?

Question

¿Conocemos algún problema de NP que tenga un límite inferior de complejidad temporal superlineal? Lo ideal sería demostrar que 3SAT tiene límites inferiores superpolinómicos, pero supongo que estamos lejos de eso. Sólo me gustaría conocer ejemplos de límites inferiores super-lineales.

Sé que el teorema de la jerarquía temporal nos da problemas que se pueden resolver en O(n^3) pero no en O(n^2), etc. Por eso puse la palabra "natural" en la pregunta.

Pido problemas en NP, porque si no alguien daría ejemplos de problemas EXP-completos.

Sé que hay compensaciones tiempo-espacio para algunos problemas en NP. Sin embargo, no sé si alguno de ellos implica un límite inferior de complejidad temporal superlineal.

(Para responder a una pregunta que se plantea a continuación sobre los modelos de máquinas, considere las máquinas de Turing de varias cintas o el modelo RAM).

Answer 1

Siento llegar tan tarde a la discusión, pero acabo de registrarme...

Existen límites inferiores de tiempo no lineal en las máquinas de Turing multicinta para problemas NP-completos. Estos límites inferiores se derivan del hecho de que la clase de problemas resolubles en tiempo lineal no determinista no es igual a la clase de los resolubles en tiempo lineal (determinista), en el entorno de la máquina de Turing multicinta. Esto se demuestra en:

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Versión preliminar) FOCS 1983: 429-438

De hecho, desentrañar la prueba muestra que debe haber algún problema solucionable en tiempo lineal no determinista que no sea solucionable en $o(n \cdot (\log^* n)^{1/4})$ tiempo (de nuevo, en una máquina de Turing de varias cintas). Obsérvese el * en el logaritmo; es sólo "apenas" superior a lineal. Una aplicación conocida de este resultado es que un problema natural NP-completo en teoría de autómatas no puede resolverse en $o(n \cdot (\log^* n)^{1/4})$ tiempo:

Etienne Grandjean: A Nontrivial Lower Bound for an NP Problem on Automata. SIAM J. Comput. 19(3): 438-451 (1990)

Desgraciadamente, el límite inferior de Paul et al. depende crucialmente de la geometría que surge al acceder a cintas unidimensionales. No sabemos cómo demostrar un límite inferior no lineal incluso si se permite que la máquina de Turing tenga un número constante de dos -cintas dimensionales. Podemos demostrar límites inferiores de tiempo para problemas NP en modelos computacionales generales si se restringe severamente el espacio de trabajo adicional utilizado por la máquina. (Esto es entrar en mi propio trabajo, así que no diré más a menos que estés realmente interesado).

En cuanto al comentario anterior: el límite inferior de la clasificación sólo es válido en un modelo basado en la comparación, que es extremadamente restringido. La afirmación de que la ordenación requiere tiempo Omega(n log n) en modelos computacionales generales es falsa. Hay algoritmos más rápidos para ordenar números enteros. Véase, por ejemplo:

Yijie Han: Deterministic sorting in O(n log logn) time and linear space. J. Algorithms 50(1): 96-105 (2004)

Answer 2

Si restringe espacio uso sea sublineal entonces se puede demostrar superlineal tiempo límites inferiores en SAT. Véase este artículo en el blog de Lipton para una buena exposición.

Answer 3

Para el modelo de circuito, la respuesta es NO. Los mejores límites inferiores generales son lineales.

(Como Ryan explicó en su respuesta y comentario, para las máquinas de Turing de varias cintas existen límites (ligeramente) superlineales. Por lo que entiendo de su comentario para las máquinas de Turing de acceso aleatorio no se conocen límites inferiores superlineales).

Answer 4

El tiempo de ejecución depende del modelo de cálculo. Por ejemplo, el problema "Dadas cadenas $s$ y $t$ ¿son idénticos?" lleva un tiempo cuadrático en una máquina de Turing de una cinta. Así que puedes dar un modelo más razonable de computación... y la siguiente persona que venga explicará cómo es demasiado fuerte, etc.

Hmmm. Quizá tu pregunta podría reformularse en términos de utilización de algún otro recurso (que a su vez requiere al menos una cantidad de tiempo determinada). Por lo tanto, tal vez inventar un problema de decisión en torno a la clasificación, y apelar a la $n\ln(n)$ límite inferior...