¿Usa la complejidad de Kolmogorov para establecer límites inferiores de la complejidad de la prueba?

11

La motivación para esta pregunta es el hecho de que la mayoría de las cadenas de n bits son incompresibles. Intuitivamente, podemos proponer por analogía que la mayoría de las pruebas para tautologías son incompresibles para el tamaño polinómico. Básicamente, mi intuición es que algunas pruebas son inherentemente aleatorias y no se pueden comprimir.

¿Existe una buena referencia sobre el esfuerzo de investigación relacionado con el uso de los resultados de complejidad de Kolmogorov para establecer límites inferiores súper polinomiales en el tamaño de prueba de las tautologías?

En este Ph.D. disertación sobre la complejidad de los sistemas de prueba proposicionales El método de incompatibilidad de Kolmogorov Complexity se utiliza para obtener el límite inferior Urquhart para una clase de tautologías. Me pregunto si hay resultados más sólidos con el método de incompatibilidad u otros resultados de la complejidad de Kolmogorov.Ω(n/log⁡n)

lower-bounds proof-complexity kolmogorov-complexity Mohammad Al-Turkistany
fuente
44
La complejidad de Kolmogorov no parece ser útil para las tautologías. Para cualquier sistema formal, la primera prueba lexicográfica de que una fórmula de bits es una tautología es de hecho extremadamente compresible: se puede describir en bits, especificando la fórmula junto con un programa que prueba todas las pruebas en algún sistema formal en orden lexicográfico. Tendría más sentido mirar versiones limitadas en el tiempo de la complejidad de Kolmogorov. nn+O(1)
Ryan Williams el
No estaba claro, me refiero a los resultados de complejidad de Kolmogorov. La pregunta está editada.
Mohammad Al-Turkistany
3
El comentario de Ryan sigue siendo apropiado, incluso después de la edición. A menos que enlace algún recurso, la complejidad de Kolmogorov de cualquier prueba es una constante (para el enumerador fijo de prueba de fuerza bruta) más el tamaño de la oración. De esta manera, no puede obtener mejores límites inferiores que los lineales.
András Salamon
2
Su pregunta se refiere específicamente a los "límites inferiores superpolinomiales". El argumento de Ryan muestra que la respuesta es trivialmente no, ya que la complejidad de Kolmogorov es a lo sumo lineal. El límite inferior de Galesi es sublineal, y mucho menos superpolinomial.
András Salamon
1
@turkistany: consulte meta.cstheory.stackexchange.com/questions/300/… .
Kaveh

Respuestas:

1

Arvind, Köbler, Mundhenk y Torán introdujeron la noción de complejidad de instancia no determinista limitada por el tiempo. Basado en una lectura rápida, parece que usan la medida de complejidad de Kolmogorov que depende del tamaño de la TM no determinista más corta. Pudieron demostrar la existencia de Tautologías difíciles de probar bajo una noción de dureza basada en la complejidad de instancia no determinista.

Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán, Complejidad de instancia no determinista y tautologías difíciles de probar,

Mohammad Al-Turkistany
fuente