Ada peluang untuk pencarian bukti yang efisien dalam logika linier, tetapi saya tidak berpikir pekerjaan saat ini menunjukkan bahwa itu lebih mudah daripada pencarian bukti dalam logika non-substruktural. Masalahnya adalah jika Anda ingin membuktikan dalam logika linier, Anda memiliki pertanyaan tambahan yang tidak Anda miliki dalam pencarian bukti normal: apakah digunakan untuk membuktikan atau digunakan untuk membuktikan ? Dalam praktiknya, "nondeterminisme sumber daya" ini adalah masalah besar dalam melakukan pencarian bukti dalam logika linier.C A C BC⊢ ( A ⊗ B )CSEBUAHCB
Bukankah pencarian bukti di LL lebih sulit daripada IL? ISTR, logika proposisional klasik adalah NP-lengkap, logika proposisional intuitionistic adalah PSPACE-complete, dan logika linear intuitionistic (with ) tidak dapat ditentukan. ! SEBUAH
Neel Krishnaswami
4
@Neel: Eksponensial adalah alat untuk menyelinap kembali kontraksi. Juga, penghubung aditif secara internal berperilaku seolah-olah mereka mengalami kontraksi, jadi Anda juga tidak menginginkannya. Yang tersisa adalah MLL, yang memang NP-complete (tidak seperti logika klasik, yang tidak NP-complete seperti yang Anda katakan, tetapi coNP-complete). Secara khusus, setiap MLL-tautologi memiliki bukti ukuran polinomial. Namun, bukti ini tidak mudah ditemukan secara deterministik, seperti yang dijelaskan Rob (yang merupakan hal yang baik, karena kami ingin NP tidak berada dalam waktu
sub-respon
1
Anda berdua melayani menunjukkan bahwa saya berbicara sangat informal tentang mengapa logika linier "tidak mudah" - dalam arti formal pencarian bukti MALL lebih sulit, dan pencarian bukti logika linier penuh masih lebih sulit. Sebagian besar, jika tidak semua, hasil yang Anda maksudkan berasal dari Lincoln et al dalam makalah 1990 "Masalah Keputusan untuk Logika Linear Proposisional."
Rob Simmons
1
@ Emil - Saya tidak pernah menempel perbedaan yang menarik antara MLL dan logika klasik. MLL dalam NP karena saksinya harus kecil ... tetapi bukti sekuensial proposisional klasik tidak perlu berukuran polinomial (dan saya kira tidak bisa, secara umum, dengan ukuran). Apa saksi polinomial untuk tidak ada-klasik-sekuens-bukti- ? Ac u tSEBUAH
Rob Simmons
1
@Rob Simmons: tugas yang memuaskan untuk negasinya.
Kaveh
11
Tidak, hanya saja lebih sulit.
Sama seperti masalah keputusan untuk logika proposisional intuitionistic lebih sulit daripada logika proposisional klasik, demikian juga logika proposisional linier masih lebih sulit. Baik dengan eksponensial (yang tidak kekurangan kontraksi) atau berbagai macam penghubung nonkomutatif, logikanya menjadi tidak dapat dipastikan dan bahkan MALL klasik yang lemah adalah PSPACE yang lengkap. Sebaliknya, masalah keputusan untuk logika proposisional klasik adalah co-NP lengkap, dan untuk logika proposisional intuitionistic, PSPACE selesai. (Begitu saja, saya tidak tahu kompleksitas MALL intuitionistic.)
Saya merekomendasikan pemaparan Pat Lincoln di bagian 6 dari logika Linear- nya , SIGACT News 1992. Kami telah belajar sedikit lebih banyak sejak itu, yaitu, kami memiliki hasil untuk keluarga besar logika linier, tetapi gambaran dasarnya ada di sana.
Dengan cara tertentu, inilah yang membuat pencarian bukti untuk logika linier menarik, karena kekerasan masalah keputusan membuat ruang untuk gagasan komputasi yang lebih menarik, dan logika linier sulit dalam banyak cara yang berbeda. Andrej menunjuk ke Tinjauan Dale Miller tentang Pemrograman Logika Linier ; ini adalah tempat yang baik untuk dilihat karena Miller telah melakukan lebih banyak untuk mengembangkan gagasan pencarian bukti sebagai perhitungan seperti orang lain.
@Kaveh: Kesalahan perhitungan daripada kesalahan ketik; tetap. Saya harus menyebutkan MLL.
Charles Stewart
11
Dengan asumsi bahwa kompleksitas masalah provabilitas akan memuaskan Anda, lanskap kompleksitas logika substruktural dengan dan tanpa kontraksi agak rumit. Saya akan mencoba mensurvei di sini apa yang dikenal dengan logika linear proposisional dan logika proposisional. Jawaban singkatnya adalah bahwa kontraksi terkadang membantu (mis. LLC dapat dipilih, sedangkan LL tidak), dan terkadang tidak (mis. MALL adalah PSPACE-complete, MALLC adalah ACKERMANN-complete).
LLW: affine logic, yaitu LL dengan pelemahan, fragmen yang sama seperti di atas
LLC: logika linier kontraktual, yaitu LL dengan kontraksi, fragmen yang sama seperti di atas
→→ , ∧
Kompleksitas Provabilitas
Lengkap NP: MLL [Kan91]
NP-lengkap: CL
Selesai PSPACE: IL [Sta79], MALL [Lin92]
→
TOWER-complete: MELLW, LLW [Laz14]
→,∧
Σ01
→
Referensi
[Kan91] Max Kanovich, Fragmen multiplikasi dari logika linier adalah NP-complete , Laporan Penelitian X-91-13, Institute for Language, Logic, and Information, 1991.
[Laz14] Ranko Lazić dan Sylvain Schmitz, Kompleksitas Non-Elementer untuk Percabangan VASS, MELL, dan Extensions , manuskrip, 2014. arXiv: 1401.6785 [cs.LO]
[Lin92] Patrick Lincoln, John Mitchell, Andre Scedrov, dan Natarajan Shankar, Masalah keputusan untuk logika linier proporsional , Annals of Pure and Applied Logic 56 (1–3): 239–311, 1992. 10.1016 / 0168-0072 (92) 90075-B
Tidak, hanya saja lebih sulit.
Sama seperti masalah keputusan untuk logika proposisional intuitionistic lebih sulit daripada logika proposisional klasik, demikian juga logika proposisional linier masih lebih sulit. Baik dengan eksponensial (yang tidak kekurangan kontraksi) atau berbagai macam penghubung nonkomutatif, logikanya menjadi tidak dapat dipastikan dan bahkan MALL klasik yang lemah adalah PSPACE yang lengkap. Sebaliknya, masalah keputusan untuk logika proposisional klasik adalah co-NP lengkap, dan untuk logika proposisional intuitionistic, PSPACE selesai. (Begitu saja, saya tidak tahu kompleksitas MALL intuitionistic.)
Saya merekomendasikan pemaparan Pat Lincoln di bagian 6 dari logika Linear- nya , SIGACT News 1992. Kami telah belajar sedikit lebih banyak sejak itu, yaitu, kami memiliki hasil untuk keluarga besar logika linier, tetapi gambaran dasarnya ada di sana.
Dengan cara tertentu, inilah yang membuat pencarian bukti untuk logika linier menarik, karena kekerasan masalah keputusan membuat ruang untuk gagasan komputasi yang lebih menarik, dan logika linier sulit dalam banyak cara yang berbeda. Andrej menunjuk ke Tinjauan Dale Miller tentang Pemrograman Logika Linier ; ini adalah tempat yang baik untuk dilihat karena Miller telah melakukan lebih banyak untuk mengembangkan gagasan pencarian bukti sebagai perhitungan seperti orang lain.
sumber
Dengan asumsi bahwa kompleksitas masalah provabilitas akan memuaskan Anda, lanskap kompleksitas logika substruktural dengan dan tanpa kontraksi agak rumit. Saya akan mencoba mensurvei di sini apa yang dikenal dengan logika linear proposisional dan logika proposisional. Jawaban singkatnya adalah bahwa kontraksi terkadang membantu (mis. LLC dapat dipilih, sedangkan LL tidak), dan terkadang tidak (mis. MALL adalah PSPACE-complete, MALLC adalah ACKERMANN-complete).
Logika Proposisional
Kompleksitas Provabilitas
Referensi
sumber
Mungkin Tinjauan Dale Miller tentang pemrograman logika linier adalah titik awal yang baik?
sumber