Super-tiempo lineal de la complejidad de los límites inferiores para cualquier natural problema en NP?

Question

No sabemos a cualquier problema en NP que tiene un super-tiempo lineal de la complejidad límite inferior? Idealmente, nos gustaría mostrar que 3SAT tiene super-polinomio límites inferiores, pero creo que estamos lejos de eso. Me gustaría saber algunos ejemplos de super-lineal límites inferiores.

Sé que el tiempo de jerarquía teorema nos da los problemas que pueden ser resueltos de O(n^3), pero no en O(n^2), etc. Por eso, he puesto la palabra "natural" en la pregunta.

Pido por problemas en NP, porque de lo contrario alguien podría dar ejemplos de EXP-completar los problemas.

Sé que hay tiempo-espacio de las desventajas de algunos de los problemas en NP. No sé si alguno de ellos implica un super-tiempo lineal de la complejidad límite inferior, aunque.

(A la dirección de una de las siguientes preguntas acerca de los modelos de máquinas, considere multitape máquinas de Turing o la memoria RAM modelo).

Answer 1

El tiempo de ejecución depende del modelo de cálculo. Por ejemplo, el problema "(m, n, p) ¿m + n = p?", se toma al menos cuadrática tiempo en una cinta de máquina de Turing. Así que usted puede dar una respuesta más razonable modelo de cálculo... y la siguiente persona para venir a lo largo de explicar cómo es demasiado fuerte, etc.

Hmmm. Tal vez su pregunta podría ser reformulado en términos de la utilización de algún otro recurso (que a su vez requiere de al menos una cantidad fija de tiempo). Así que tal vez inventar un problema de decisión en torno a la clasificación, y apelar a la nlog(n) límite inferior...

Answer 2

La respuesta corta es NO. El mejor general de los límites inferiores son lineales.

Answer 3

Lo siento, soy tan tarde a la discusión, pero me acabo de registrar...

Hay tiempo no-lineal límites inferiores en multitape máquinas de Turing para NP-completo los problemas. Estos límites inferiores a seguir, desde el hecho de que la clase de problemas que tienen solución no determinista en tiempo lineal no es igual a la clase de aquellos que tienen solución en (determinista) el tiempo lineal, en el multitape máquina de Turing estableciendo. Esto queda demostrado en:

Wolfgang J. Pablo, Nicolás Pippenger, Endre Szemerédi, William T. Trotter: En el Determinismo versus No-Determinismo y Problemas Relacionados (Versión Preliminar) FOCS 1983: 429-438

De hecho, el desentrañamiento de la prueba muestra que debe haber algún problema solucionable, no determinista en tiempo lineal que no es solucionable en $o(n \cdot (\log^* n)^{1/4})$ tiempo (de nuevo, en un multitape máquina de Turing). Nota * en el logaritmo; esto es sólo "apenas" por encima lineal. Una conocida aplicación de este resultado es que un natural NP-completos problema en la teoría de autómatas, no puede ser resuelto en $o(n \cdot (\log^* n)^{1/4})$ tiempo:

Etienne Grandjean: Un Trivial límite Inferior de una NP Problema en Autómatas. SIAM J. Comput. 19(3): 438-451 (1990)

Por desgracia, el límite inferior de Pablo et al. depende fundamentalmente de la geometría que surge de acceder a una dimensión de las cintas. No sabemos cómo probar un no-lineal límite inferior incluso si usted permite que la máquina de Turing para tener un número constante de dosdimensiones de las cintas. Podemos probar el tiempo de los límites inferiores de la NP problemas en general los modelos de cálculo si usted restringir severamente el extra de espacio de trabajo utilizado por la máquina. (Este es entrar en mi propio trabajo, así que no voy a decir más, a menos que usted está realmente interesado.)

Como para el comentario anterior: el límite inferior de la clasificación sólo se aplica en una comparación basada en el modelo, que se encuentra muy restringido. La afirmación de que la clasificación requiere Omega(n log n) en general, los modelos computacionales es falso. Hay más rápido de los algoritmos para la clasificación de los números enteros. Véase, por ejemplo:

Yijie Han: Determinista de la clasificación en O(n log logn) tiempo y espacio lineal. J. Algoritmos 50(1): 96-105 (2004)

Answer 4

Si restringe el espacio de uso para ser sublinear a continuación, puede probar signos diacríticos tiempo los límites inferiores en el SAT. Ver este artículo en Lipton del blog para una buena exposición.