Verwenden Sie die Kolmogorov-Komplexität, um die unteren Grenzen der Beweiskomplexität festzulegen?

11

Die Motivation für diese Frage ist die Tatsache, dass die meisten n-Bit-Strings inkompressibel sind. Intuitiv können wir analog vorschlagen, dass die meisten Beweise für Tautologien für die Polynomgröße inkompressibel sind. Grundsätzlich ist meine Intuition, dass einige Beweise von Natur aus zufällig sind und nicht komprimiert werden können.

Gibt es eine gute Referenz zu Forschungsanstrengungen im Zusammenhang mit der Verwendung von Kolmogorov-Komplexitätsergebnissen, um superpolynomielle Untergrenzen für die Beweisgröße von Tautologien festzulegen?

In diesem Ph.D. Dissertation über die Komplexität aussagekräftiger Beweissysteme Die Inkomprimierbarkeitsmethode von Kolmogorov Complexity wird verwendet, um die Untergrenze von Urquharts für eine Klasse von Tautologien zu erhalten. Ich frage mich, ob es stärkere Ergebnisse mit der Inkompressibilitätsmethode oder andere Ergebnisse aus der Kolmogorov-Komplexität gibt.Ω(n/log⁡n)

lower-bounds proof-complexity kolmogorov-complexity Mohammad Al-Turkistany
quelle
4
Die Komplexität von Kolmogorov scheint für Tautologien nicht nützlich zu sein. Für jedes formale System ist der lexikographisch erste Beweis, dass eine Bit-Formel eine Tautologie ist, tatsächlich extrem komprimierbar: Er kann in n + O ( 1 ) -Bits beschrieben werden , indem die Formel zusammen mit einem Programm angegeben wird, das alle Beweise versucht ein formales System in lexikographischer Reihenfolge. Es wäre sinnvoller, zeitlich begrenzte Versionen der Kolmogorov-Komplexität zu betrachten. nn+O(1)
Ryan Williams
Ich war nicht klar, ich meine Kolmogorov Komplexität Ergebnisse. Frage wird bearbeitet.
Mohammad Al-Turkistany
3
Ryans Kommentar ist auch nach der Bearbeitung noch angebracht. Sofern Sie keine Ressource gebunden haben, ist die Kolmogorov-Komplexität eines Beweises eine Konstante (für den festen Brute-Force-Beweis-Enumerator) plus die Größe des Satzes. Auf diese Weise können Sie keine besseren Untergrenzen als linear erhalten.
András Salamon
2
Ihre Frage bezieht sich speziell auf "Superpolynom-Untergrenzen". Ryans Argument zeigt, dass die Antwort trivial nein ist, da die Kolmogorov-Komplexität höchstens linear ist. Galesis Untergrenze ist sublinear, geschweige denn superpolynomisch.
András Salamon
1
@turkistany: siehe meta.cstheory.stackexchange.com/questions/300/… .
Kaveh

Antworten:

1

Arvind, Köbler, Mundhenk und Torán führten den Begriff der zeitlich begrenzten nichtdeterministischen Instanzkomplexität ein. Basierend auf einer schnellen Ablesung scheint es, dass sie Kolmogorov-Komplexitätsmaß verwenden, das von der Größe des kürzesten nichtdeterministischen TM abhängt. Sie konnten die Existenz schwer zu beweisender Tautologien unter dem Begriff der Härte beweisen, der auf der Komplexität nichtdeterministischer Instanzen basiert.

Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán, Komplexität nichtdeterministischer Instanzen und schwer zu beweisende Tautologien,

Mohammad Al-Turkistany
quelle