Baru-baru ini saya mulai membaca banyak tentang kompleksitas bukti dan sangat menikmati apa yang saya baca. Saya benar-benar ingin belajar lebih banyak tentang ini, tetapi saya mengalami kesulitan menemukan beberapa bahan pemula yang baik untuk memulai. Adakah yang bisa merekomendasikan beberapa hal mendasar?
cc.complexity-theory
lo.logic
proof-complexity
Yugioh Mishima
sumber
sumber
Jawaban:
Tergantung pada level "pemula" seperti apa yang ingin Anda miliki. Saya tidak berpikir ada teks tingkat sarjana yang bagus tentang kompleksitas bukti (ini mungkin berlaku untuk sebagian besar sub-bidang khusus dalam kompleksitas). Tetapi untuk sumber pemula (tingkat pascasarjana), saya akan merekomendasikan, sesuatu seperti memahami dengan baik ukuran eksponensial dasar yang lebih rendah pada sanggahan resolusi prinsip pigeonhole (melalui pembatasan acak, pengorbanan ukuran lebar dan interpolasi yang layak), dan untuk memperluas dari itu menunjuk lebih jauh. Ini dapat dicapai (kurang-lebih) sebagai berikut:
Stasys Jukna, Combinatorics Extremal Dengan Aplikasi dalam Ilmu Komputer, 2001, Springer-Verlag, Bagian 4.8.
Eli Ben-sasson dan Avi Wigderson, Bukti Singkatnya Sempit - Resolusi Dibuat Sederhana (2000), JACM.
P. Beame dan T. Pitassi, Kompleksitas bukti proposisional: Masa lalu, sekarang, dan masa depan, Tren terkini dalam ilmu komputer teoretis: Memasuki abad ke-21 (G. Paul, G. Rozenberg, dan A. Salomaa, editor), World Scientific Publishing , 2001, hlm. 42--70.
Pavel Pudlák, Batas bawah untuk resolusi dan memotong bukti pesawat terbang dan perhitungan monoton, Journal of Symbolic Logic, vol. 62 (1997), no. 3, hlm. 981-998.
Anda juga dapat membaca teks yang lebih lengkap dan panjang:
Untuk sisi kompleksitas bukti yang lebih logis , seperti yang disarankan Kaveh, Anda dapat mulai membaca bab pertama dari:
sumber
Untuk sisi yang lebih aljabar dari kompleksitas bukti, saya sarankan memulai dengan makalah survei Pitassi tahun 1996:
Untuk tinjauan singkat, Anda juga dapat membaca Bab 5 buku Clote - Kranakis yang telah disebutkan oleh Iddo, yang memiliki bagian tentang sistem bukti aljabar.
Makalah penelitian pertama yang saya sarankan membaca (baik karena itu mani dan karena itu bacaan yang menyenangkan) adalah makalah di mana sistem bukti Kalkulus Groebner atau Polinomial diperkenalkan:
sumber
Saya menemukan catatan kuliah pengantar ini mudah dibaca: Kuliah IAS Paul Beame
sumber
Survei kompleksitas bukti tujuan umum terbaru dan terkini mungkin dari survei Nathan Segerlind:
Nathan Segerlind: Kompleksitas Bukti Proposisi. Buletin Simbolik Logika 13 (4): 417-481, 2007 ( http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps ).
Dan sekarang, peringatan untuk dua colokan diri yang tidak tahu malu ...
Sebuah survei yang bahkan lebih baru, tetapi lebih sempit berfokus pada pertanyaan tentang ukuran bukti, ruang bukti, dan trade-off ukuran ruang, adalah:
Jakob Nordström. Game Pebble, Kompleksitas Bukti, dan Trade-off Time-Space. Metode logis dalam Ilmu Komputer, volume 9, edisi 3, artikel 15, September 2013 ( http://www.lmcs-online.org/ojs/viewarticle.php?id=674 ).
Ada juga beberapa catatan kuliah dari kursus yang agak baru saya berikan pada "spektrum low-end" kompleksitas bukti (yaitu, sistem bukti yang relatif lemah seperti resolusi, kalkulus polinomial, dan memotong pesawat) dan koneksi ke pemecahan SAT. Catatan-catatan ini dapat ditemukan di http://www.csc.kth.se/~jakobn/teaching/proofcplx11/#scribe-notes (beberapa masih dalam proses tetapi yang tersedia harus dalam kondisi baik).
sumber