Kompleksitas modal logika IK5

Apa kompleksitas masalah kepuasan lokal untuk modal logika ? Di sini kita dilambangkan oleh logika modal atas bingkai euclidean diperpanjang dengan modalitas terbalik. Bisakah Anda memberikan referensi? Apakah dalam ? $\mathit{IK5}$ $IK5$ $NP$

Apa yang saya ketahui tentang topik ini?

Sangat mudah untuk melihat bahwa ada di , karena ada pengurangan dari itu ke (fragmen dijaga dua variabel logika tingkat pertama) - lihat Memutuskan Logika Tata Bahasa Reguler dengan Converse Melalui Logika Orde Pertama . $IK5$ $ExpTime$ $GF^2$

Di sisi lain, biasa adalah -complete. $K5$ $NP$

Kita dapat menulis rumus equisatisfiable di (fragmen satu-variabel logika orde pertama), karena model dapat dibagi menjadi tiga bagian: (1) mulai dunia , (2) sucessors dari (3) sucessors penggantinya . Contoh pengurangan untuk logika lebih keras ( dengan modalitas bergradasi) dijelaskan dalam Catatan atas Kompleksitas Masalah satisfiability untuk Graded Modal Logika . Namun dengan adanya modalitas terbalik kita tidak dapat melakukan trik yang sama - ide singkatnya adalah bahwa dunia terbalik dapat membutuhkan jumlah penggantinya yang berbeda. $FO^1$ $w$ $w$ $w$ $K5$

cc.complexity-theory complexity-classes lo.logic modal-logic Bartosz Bednarczyk
sumber

Logikanya EXP-complete. Salah satu cara untuk membuktikan batas bawah adalah dengan mencatat bahwa KTB logika ditambah dengan modalitas universal, atau bahkan hanya hubungan konsekuensi global KTB, adalah EXP-complete (Chen dan Lin [1]; perhatikan bahwa mereka menyatakan KTB sebagai B).

$(W,R,R^{-1})$ $C$ $I$ $R$ $C$

R_{s} := {(x, y) \in C^{2} : \exists z \in I (R (z, x) \land R (z, y))}

$R_s:=\{(x,y)\in C^2:\exists z\in I\,(R(z,x)\land R(z,y))\}$

C

$C$

C

$C$

I

$I$

R_{s}

$R_s$

⊢_{{K T B}^{U}} ϕ ⟺ ⊢_{I K 5} ◊^{-} ⊤ \land ◻^{+} ◊^{-} ◻^{-} ⊥ \to ϕ^{*},

${}\vdash_{\mathrm{KTB}^U}\phi\iff{}\vdash_{\mathrm{IK5}}\Diamond^-\top\land\Box^+\Diamond^-\Box^-\bot\to\phi^*,$

$\phi^*$

\begin{aligned} (◻ ϕ)^{*} & = ◻^{-} (◻^{-} ⊥ \to ◻^{+} ϕ^{*}), \\ (A ϕ)^{*} & = ◻^{+} ϕ^{*} . \end{aligned}

$\begin{align*} (\Box\phi)^*&=\Box^-(\Box^-\bot\to\Box^+\phi^*),\\ (A\phi)^*&=\Box^+\phi^*. \end{align*}$

$A$ $\mathrm{KTB}^U$ $\Box^+$ $\Box^-$

Referensi:

[1] Cheng-Chia Chen dan I-Peng Lin, Kompleksitas teori modal proposisional dan kompleksitas konsistensi teori modal proposisional , dalam: Proc. LFCS 1994 (Anil Nerode dan Yu. V. Matiyasevich, eds.), LNCS 813, Springer, hlm. 69–80, doi 10.1007 / 3-540-58140-5_8 .

Emil Jeřábek
sumber

Mungkin pertanyaan konyol. Sejauh yang saya mengerti, Anda membuktikan bahwa konsekuensi global dalam IK5 setidaknya sekeras konsekuensi global dalam KTB ^ U. Karena kepuasan lokal adalah kasus khusus masalah konsekuensi global, bagaimana kita mendapatkan kekerasan untuk itu?

Bartosz Bednarczyk

Tidak, saya membuktikan bahwa teorema (yang merupakan kasus khusus dari konsekuensi lokal dan global) dalam IK5 setidaknya sekeras teorema dalam KTB ^ U. Atau pada akhirnya, kepuasan di IK5 sama sulitnya dengan kepuasan di KTB ^ U. Karena itu, itu tidak benar-benar membuat perbedaan: konsekuensi lokal dan teorema memiliki kompleksitas yang sama dalam setiap logika modal oleh teorema deduksi, dan konsekuensi lokal dan global memiliki kompleksitas yang sama dalam setiap logika dengan modalitas universal yang dapat ditentukan (yang dimiliki IK5 memiliki ).

Emil Jeřábek

Emil Jeřábek, apakah Anda mengetahui adanya hasil batas atas untuk IK5? Berbagai teknik kemudian diterjemahkan ke GF2, yang saya sebutkan di posting saya?

Bartosz Bednarczyk

2^{O (n)}

$2^{O(n)}$

Pertanyaan terakhir. Bisakah Anda memberi tahu saya jika hasil itu memberi kita juga terikat pada masalah kepuasan global (saya tidak akrab dengan teorema, itu sebabnya saya bertanya)? Sangat mudah untuk mengurangi kepuasan global ke kepuasan lokal jika Anda dapat menggunakan modalitas universal, tetapi mungkin batas atas untuk IK5 lebih kecil dari Exp.

Bartosz Bednarczyk

Kompleksitas modal logika IK5

Jawaban: