Teori Kompleksitas yang Diverifikasi Secara Resmi

18

Apakah ada proyek yang sedang berlangsung untuk secara formal memverifikasi teorema dan bukti teori kompleksitas menggunakan asisten bukti seperti Coq? Apakah ada batasan untuk melakukan ini?

cc.complexity-theory complexity proof-assistants Samuel Schlesinger
sumber
3
Saya pikir beberapa penelitian sedang dilakukan di University of Bologna dengan asisten bukti Matita. Lihat misalnya Memformalkan Mesin Turing .
Marzio De Biasi
Terkait: cstheory.stackexchange.com/q/4052/129 . Beberapa jawaban bahkan berbicara tentang Coq, dan yang lain menyebutkan hasil yang dapat diartikan sebagai hambatan teoretis untuk proyek ini, meskipun kemungkinan mereka bukan hambatan dalam praktiknya.
Joshua Grochow
Terima kasih, pertanyaan itu luar biasa @JoshuaGrochow, sangat senang saya mengetahui tentang monograf Hartmannis itu. Jika saya mengerti, penghalang kemudian akan memastikan bahwa kelas kompleksitas yang Anda tetapkan adalah apa yang Anda pikir mereka bukan versi "dapat dibuktikan dalam Coq".
Samuel Schlesinger
1
Ada jawaban untuk pertanyaan serupa di sini , meskipun ini lebih tentang membuktikan batas kompleksitas spesifik daripada hasil teori kompleksitas umum
jmite
Benar itu relevan sekalipun. Saya ingin tahu tentang cara-cara di mana sistem tipe yang mendasarinya dapat membantu, seperti dengan memasukkan beberapa gagasan kompleksitas dalam jenis fungsi. Tentu saja ini akan mengarah ke berbagai persamaan, tetapi saya pikir itulah yang kita miliki dalam kompleksitas secara alami.
Samuel Schlesinger

Jawaban:

6

Dalam makalah berikut ini, kolega saya, Uli Schöpp, menyajikan verifikasi formal (dalam Coq) dari hasil nontrivial oleh Cook dan Rackoff pada kekuatan komputasi graph automata. https://scholar.google.at/scholar?oi=bibs&cluster=4944920843669159892&btnI=1&hl=de (Schöpp, U. (2008). Batas bawah yang diformalkan pada tingkat keterjangkauan yang tidak terarah. Dalam Logika untuk Pemrograman, Kecerdasan Buatan, dan Penalaran ( hlm. 621-635). Springer Berlin / Heidelberg.)

Martin Hofmann
sumber
1
Bisakah Anda memberikan referensi lengkap sehingga jawabannya tidak tergantung pada validitas tautan?
Serigala