Komplexität der Modallogik IK5

Was ist die Komplexität des lokalen Erfüllbarkeitsproblems für modale Logik ? Hier bezeichnen wir mit die Modallogik über euklidische Rahmen, die mit inverser Modalität erweitert wurden. Könnten Sie Referenzen angeben? Ist es in ? $\mathit{IK5}$ $IK5$ $NP$

Was weiß ich über das Thema?

Es ist leicht zu erkennen, dass sich in , da es eine Reduktion von (dem zwei Variablen geschützten Fragment der Logik erster Ordnung) gibt - siehe Entscheiden einer regulären Grammatiklogik mit Converse Through First-Order-Logik . $IK5$ $ExpTime$ $GF^2$

Auf der anderen Seite, die gewöhnliche ist - vollständig. $K5$ $NP$

Wir können eine nicht zufriedenstellende Formel in (das einvariable Fragment der Logik erster Ordnung) schreiben , weil die Modelle in drei Teile unterteilt werden können: (1 ) Startwelt , (2) Nachfolger von (3) Nachfolger von Nachfolgern von . Die beispielhafte Reduzierung für noch härtere Logik ( mit abgestuften Modalitäten) ist in A Hinweis zur Komplexität des Erfüllbarkeitsproblems für abgestufte Modallogiken beschrieben . Bei inverser Modalität können wir jedoch nicht denselben Trick ausführen - die kurze Idee ist, dass inverse Welten die unterschiedliche Anzahl von Nachfolgern erfordern könnten. $FO^1$ $w$ $w$ $w$ $K5$

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

Die Logik ist EXP-vollständig. Eine Möglichkeit, die Untergrenze zu beweisen, besteht darin, festzustellen, dass die mit universeller Modalität erweiterte logische KTB oder sogar nur die globale Konsequenzbeziehung von KTB EXP-vollständig ist (Chen und Lin [1]; beachten Sie, dass sie KTB als B bezeichnen).

Es ist zu beachten, dass ein verbundener IK5-Rahmen entweder ein einzelner irreflexiver Punkt ist oder aus einem reflexiven Cluster zusammen mit einer (möglicherweise leeren) Menge von irreflexiven Punkten besteht, von denen jeder sieht (in ) , die eine nicht - leere Teilmenge von . Somit ist ist eine symmetrische Beziehung auf ;; Wenn jedes Element von von einem Element von , ist auch reflexiv. Umgekehrt ist leicht zu erkennen, dass jeder reflexive symmetrische Rahmen auf diese Weise erhalten werden kann. Es folgt dem $(W,R,R^{-1})$ $C$ $I$ $R$ $C$

{R.}_{s} : = {(x, y) \in {C.}^{2} :: \exists z \in ich (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.}} ϕ ⟺ ⊢_{ich K. 5} ◊^{- -} ⊤ \land ◻^{+} ◊^{- -} ◻^{- -} ⊥ \to ϕ^{*},

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

wobei die Übersetzung mit aussagekräftigen Konnektiven pendelt und für Modaloperatoren durch definiert ist $\phi^*$

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

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

Hier bezeichnet die universelle Modalität von , und und bezeichnen jeweils die Vorwärts- und Rückwärtsmodalitäten von IK5. $A$ $\mathrm{KTB}^U$ $\Box^+$ $\Box^-$

Referenz:

[1] Cheng-Chia Chen und I-Peng Lin, Die Komplexität von Aussagenmodal-Theorien und die Komplexität der Konsistenz von Aussagenmodal-Theorien , in: Proc. LFCS 1994 (Anil Nerode und Yu. V. Matiyasevich, Hrsg.), LNCS 813, Springer, S. 69–80, doi 10.1007 / 3-540-58140-5_8 .

Emil Jeřábek
quelle

Vielleicht eine dumme Frage. Soweit ich weiß, haben Sie bewiesen, dass die globale Konsequenz in IK5 mindestens so schwer ist wie die globale Konsequenz in KTB ^ U. Wie erhalten wir die Härte dafür, da die lokale Erfüllbarkeit ein Sonderfall des globalen Konsequenzproblems ist?

Bartosz Bednarczyk

Nein, ich habe bewiesen, dass die Theoremität (die sowohl ein Sonderfall lokaler als auch globaler Konsequenzen ist) in IK5 mindestens so schwer ist wie die Theoremität in KTB ^ U. Oder doppelt ist die Erfüllbarkeit in IK5 genauso schwierig wie die Erfüllbarkeit in KTB ^ U. Allerdings macht es keinen wirklichen Unterschied: Lokale Konsequenz und Theoremie haben in jeder Modallogik nach dem Deduktionssatz die gleiche Komplexität, und lokale und globale Konsequenz haben in jeder Logik mit einer definierbaren universellen Modalität (die IK5 hat) die gleiche Komplexität ).

Emil Jeřábek

Emil Jeřábek, sind Ihnen die Ergebnisse der Obergrenze für IK5 bekannt? Verschiedene Techniken, die dann in GF2 übersetzt werden, die ich in meinem Beitrag erwähnt habe?

Bartosz Bednarczyk

2^{O (n)}

$2^{O(n)}$

Die letzte Frage. Können Sie mir sagen, ob dieses Ergebnis uns auch ein Problem mit der globalen Erfüllbarkeit gibt (ich bin mit Theoremhood nicht vertraut, deshalb frage ich)? Es ist einfach, die globale Erfüllbarkeit auf die lokale Erfüllbarkeit zu reduzieren, wenn Sie die universelle Modalität verwenden können, aber möglicherweise ist die Obergrenze für IK5 kleiner als Exp.

Bartosz Bednarczyk

Komplexität der Modallogik IK5

Antworten: