¿Cuáles son los mejores límites inferiores actuales para el tiempo y la profundidad del circuito para 3SAT?
fuente
¿Cuáles son los mejores límites inferiores actuales para el tiempo y la profundidad del circuito para 3SAT?
Hasta donde sé, el límite inferior de tiempo "independiente del modelo" más conocido para SAT es el siguiente. Deje que y S sean el tiempo de ejecución y el espacio de cualquier algoritmo SAT. Entonces debemos tener T ⋅ S ≥ n 2 cos ( π / 7 ) - o ( 1 ) infinitamente a menudo. Nota 2 cos ( π / 7 ) ≈ 1.801 http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf . (El resultado que cita Suresh es un poco obsoleto). Este resultado apareció en STACS 2010, pero ese es un resumen extendido de un artículo mucho más largo, que puede obtener aquí:
Por supuesto, el trabajo anterior se basa en muchos trabajos anteriores que se mencionan en el blog de Lipton (ver la respuesta de Suresh). Además, a medida que el límite de espacio S se acerca a n, el límite inferior de tiempo T también se acerca a n. Puede probar una mejor "compensación espacio-tiempo" en este régimen; ver la encuesta de Dieter van Melkebeek sobre los límites inferiores del espacio de tiempo SAT desde 2008.
Si se limita a las máquinas de Turing multitapa, puede probar infinitamente a menudo. Eso fue demostrado por Rahul Santhanam, y se deduce de un límite inferior similar conocido por PALINDROMES en este modelo. Creemos que debería ser capaz de probar un límite inferior cuadrático que sea "independiente del modelo" pero que haya sido difícil de alcanzar por algún tiempo.
Para circuitos no uniformes con fan-in acotado, no conozco un límite inferior de profundidad mejor que .
fuente
fuente
Entiendo lo mismo que Lev Reyzin. Es posible que exista un algoritmo determinista completo para SAT que se ejecuta en el espacio O (n) y en el tiempo O (n). Es sorprendente que no esté prohibida la existencia de un algoritmo tan eficiente.
fuente