Límites inferiores en informática teórica

Question

Además del clásico: no se puede hacer una ordenación por comparación más rápida que (n logn); ¿qué otros límites inferiores conocemos para los algoritmos? No consigo encontrarlos en google scholar, pero deben existir.

Estoy especialmente interesado en algoritmos de tiempo polinómico (es decir, y no pruebas de: no se puede resolver esto en tiempo polinómico a menos que P = NP).

Gracias.

Nota: marcado como wiki comunitario ahora

Answer 1

Cualquier lengua no regular no puede decidirse en $o(\log \log n)$ espacio. Se trata de un ejercicio de Papadimitriou Complejidad computacional, pero no lo tengo a mano.

Answer 2

Cualquier máquina de Turing de una cinta que decida el lenguaje de los palíndromos requiere $\Omega(n^2)$ tiempo. Se puede demostrar utilizando la complejidad de la comunicación. La prueba puede encontrarse en "Communication complexity" de Kushilevitz y Nisan.

$\mathbf{SAT}$ no puede decidirse a tiempo $O(n^{1.801})$ y el espacio $O(n^{o(1)})$ . Este resultado es de Ryan Williams.

Existe una tesis doctoral de Mihai Patrascu, en la que demuestra varios límites inferiores para estructuras de datos, pero más o menos son logarítmicos.

Otro buen límite inferior es el siguiente. Supongamos que tenemos una sentencia de primer orden sobre reales con operaciones '+', '*', '>' y constantes enteras. El famoso resultado de Tarski y Seidenberg afirma que se puede decidir si la sentencia es verdadera. Pero hay un resultado incondicional que requiere un tiempo exponencial.

Answer 3

No EXPTIME -puede resolverse en tiempo polinómico como consecuencia de la teorema de la jerarquía temporal . Por supuesto, lo mismo es válido para problemas más difíciles, como problemas completos para espacio exponencial, tiempo doblemente exponencial, etc. Estos resultados son incondicionales (es decir, no dependen de P ≠ NP u otras conjeturas).

Hay algunos problemas interesantes que se pueden demostrar P una de ellas se refiere a la equivalencia de las expresiones regulares (véanse estas diapositivas para una introducción), y algunos tipos de juego también son muy difíciles de resolver.

Answer 4

De la página de wikipedia de multiplicación de matrices :

Raz (2002) demuestra un límite inferior de $\Omega(m^2\log m)$ para circuitos aritméticos de coeficiente limitado sobre los números reales o complejos.

Answer 5

Hay una serie de límites inferiores para problemas relacionados con la clasificación, por ejemplo la distinción de elementos: ¿hay dos elementos idénticos en un conjunto? Estos límites inferiores son realmente interesantes porque generalizan el límite inferior de comparación a formulaciones más algebraicas: por ejemplo, se puede demostrar que resolver la distinción de elementos en un modelo que permite operaciones algebraicas tiene un límite inferior mediante el análisis de los números betti del espacio inducido por diferentes respuestas al problema.

Un ejemplo muy interesante de una cota inferior determinista exponencial incondicional (es decir, no relacionada con P frente a NP) es la estimación del volumen de un politopo. Hay una construcción debida a Furedi y Barany que muestra que el volumen de un politopo convexo no puede ser aproximado dentro de un factor exponencial en tiempo polinómico incondicionalmente. Esto es sorprendente porque existen algoritmos aleatorios en tiempo polinómico que producen aproximaciones arbitrariamente buenas.