Utiliser la complexité de Kolmogorov pour établir des limites inférieures de complexité de preuve?

11

La motivation de cette question est le fait que la plupart des chaînes de n bits sont incompressibles. Intuitivement, nous pouvons proposer par analogie que la plupart des preuves pour les tautologies sont incompressibles à la taille polynomiale. Fondamentalement, mon intuition est que certaines preuves sont intrinsèquement aléatoires et ne peuvent pas être compressées.

Existe-t-il une bonne référence sur les efforts de recherche liés à l'utilisation des résultats de complexité de Kolmogorov pour établir des limites inférieures super-polynomiales sur la taille de preuve des tautologies?

Dans ce doctorat. mémoire sur la complexité des systèmes de preuve propositionnelle la méthode d'incompressibilité de Kolmogorov Complexity est utilisée pour obtenir la borne inférieure Urquhart pour une classe de tautologies. Je me demande s'il y a des résultats plus forts en utilisant la méthode de l'incompressibilité ou d'autres résultats de la complexité de Kolmogorov?Ω(n/Journal⁡n)

lower-bounds proof-complexity kolmogorov-complexity Mohammad Al-Turkistany
la source
4
La complexité de Kolmogorov ne semble pas utile pour les tautologies. Pour tout système formel, la première preuve lexicographique qu'une formule à bits est une tautologie est en fait extrêmement compressible: elle peut être décrite en bits, en spécifiant la formule avec un programme qui essaie toutes les preuves en un certain système formel dans l'ordre lexicographique. Il serait plus logique d'examiner les versions limitées dans le temps de la complexité de Kolmogorov. n + O ( 1 )nn+O(1)
Ryan Williams
Je n'étais pas clair, je veux dire les résultats de complexité Kolmogorov. La question est modifiée.
Mohammad Al-Turkistany
3
Le commentaire de Ryan est toujours approprié, même après le montage. Sauf si vous avez lié une ressource, la complexité de Kolmogorov de toute preuve est une constante (pour l'énumérateur de preuve de force brute fixe) plus la taille de la phrase. Ainsi, vous ne pouvez pas obtenir de meilleures limites inférieures que linéaires.
András Salamon
2
Votre question porte spécifiquement sur les "bornes inférieures super-polynomiales". L'argument de Ryan montre que la réponse est non, car la complexité de Kolmogorov est tout au plus linéaire. La limite inférieure de Galesi est sublinéaire, et encore moins superpolynomiale.
András Salamon
1
@turkistany: veuillez consulter meta.cstheory.stackexchange.com/questions/300/… .
Kaveh

Réponses:

1

Arvind, Köbler, Mundhenk et Torán ont introduit la notion de complexité d'instance non déterministe limitée dans le temps. Sur la base d'une lecture rapide, il semble qu'ils utilisent une mesure de complexité de Kolmogorov qui dépend de la taille de la MT non déterministe la plus courte. Ils ont pu prouver l'existence de Tautologies difficiles à prouver sous une notion de dureté basée sur une complexité d'instance non déterministe.

Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán, Complexité des instances non déterministes et tautologies difficiles à prouver,

Mohammad Al-Turkistany
la source