Menggunakan kompleksitas Kolmogorov untuk menetapkan kompleksitas bukti dengan batas yang lebih rendah?

11

Motivasi untuk pertanyaan ini adalah fakta bahwa sebagian besar string n-bit tidak dapat dimampatkan. Secara intuitif, kita dapat mengusulkan dengan analogi bahwa sebagian besar bukti untuk Tautologi tidak dapat dikompresi dengan ukuran polinomial. Pada dasarnya, intuisi saya adalah bahwa beberapa bukti secara inheren acak dan tidak dapat dikompresi.

Apakah ada referensi yang baik pada upaya penelitian terkait dengan menggunakan hasil kompleksitas Kolmogorov untuk menetapkan batas bawah super-polinomial pada ukuran bukti Tautologi?

Dalam Ph.D. Disertasi Mengenai Kompleksitas Sistem Bukti Proposisi metode Incompressibility dari Kolmogorov Complexity digunakan untuk mendapatkan batas bawah Urquhart untuk kelas Tautologi. Saya ingin tahu apakah ada hasil yang lebih kuat menggunakan metode Incompressibility atau hasil lain dari kompleksitas Kolmogorov?Ω(n/log⁡n)

lower-bounds proof-complexity kolmogorov-complexity Mohammad Al-Turkistany
sumber
4
Kompleksitas Kolmogorov tampaknya tidak akan berguna untuk Tautologi. Untuk sistem formal apa pun, bukti leksikografis pertama bahwa rumus bit adalah tautologi sebenarnya sangat dapat dikompresi: ia dapat dijelaskan dalam n + O ( 1 ) bit, dengan menentukan rumus bersama dengan program yang mencoba semua bukti dalam beberapa sistem formal dalam urutan leksikografis. Akan lebih masuk akal untuk melihat versi kompleksitas Kolmogorov yang dibatasi waktu. nn+O(1)
Ryan Williams
Saya tidak jelas, maksud saya hasil kompleksitas Kolmogorov. Pertanyaan diedit.
Mohammad Al-Turkistany
3
Komentar Ryan masih tepat, bahkan setelah diedit. Kecuali jika Anda mengikat beberapa sumber daya, kompleksitas Kolmogorov dari bukti apa pun adalah konstan (untuk enumerator bukti brute-force tetap) ditambah ukuran kalimat. Jadi dengan cara ini Anda tidak bisa mendapatkan batas bawah yang lebih baik daripada linier.
András Salamon
2
Pertanyaan Anda secara khusus bertanya tentang "batas bawah super polinomial". Argumen Ryan menunjukkan bahwa jawabannya sepele tidak, karena kompleksitas Kolmogorov paling linear. Batas bawah Galesi adalah sublinear, apalagi superpolinomial.
András Salamon
1
@turkistany: silakan lihat meta.cstheory.stackexchange.com/questions/300/… .
Kaveh

Jawaban:

1

Arvind, Köbler, Mundhenk, dan Torán memperkenalkan gagasan kompleksitas instance nondeterministic yang terikat waktu. Berdasarkan bacaan cepat, Tampaknya mereka menggunakan ukuran kompleksitas Kolmogorov yang tergantung pada ukuran TM nondeterministic terpendek. Mereka mampu membuktikan keberadaan sulit untuk membuktikan Tautologi di bawah gagasan kekerasan berdasarkan kompleksitas contoh nondeterministic.

Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán, Kompleksitas Instansi Nondeterministik dan Tautologi yang Sulit Dibuktikan,

Mohammad Al-Turkistany
sumber