Complejidad de la lógica modal IK5

¿Cuál es la complejidad del problema de satisfacción local para la lógica modal ? Aquí denotamos por la lógica modal sobre tramas euclidianas extendidas con modalidad inversa. ¿Podría darnos alguna referencia? ¿Está en ? $\mathit{IK5}$ $IK5$ $NP$

¿Qué sé sobre el tema?

Es fácil ver que está en , ya que hay una reducción de esto a (el fragmento protegido de dos variables de la lógica de primer orden) - vea Decidir las lógicas de gramática regular con la conversión a través de la lógica de primer orden . $IK5$ $ExpTime$ $GF^2$

Por otro lado, el ordinario es completo. $K5$ $NP$

Podemos escribir una fórmula equisatisfactable en (el fragmento de una variable de la lógica de primer orden), porque los modelos se pueden dividir en tres partes: (1) mundo inicial , (2) sucesores de (3) sucesores de sucesores de . El ejemplo de reducción para una lógica aún más difícil ( con modalidades graduadas) se describe en una nota sobre la complejidad del problema de satisfacción para las lógicas modales graduadas . Sin embargo, en presencia de la modalidad inversa, no podemos hacer el mismo truco: la breve idea es que los mundos inversos podrían requerir un número diferente de sucesores. $FO^1$ $w$ $w$ $w$ $K5$

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

La lógica es EXP-complete. Una forma de probar el límite inferior es observar que la lógica KTB aumentada con la modalidad universal, o incluso la relación de consecuencia global de KTB, es EXP-complete (Chen y Lin [1]; tenga en cuenta que denotan KTB como B).

Tenga en cuenta que un marco IK5 conectado es un punto irreflexivo único o consiste en un grupo reflexivo junto con un conjunto (posiblemente vacío) de puntos irreflexivos, cada uno de los cuales ve (en ) un subconjunto no vacío de . Por lo tanto, es una relación simétrica en ; si cada elemento de es visto por un elemento de , $(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$ También es reflexivo. Por el contrario, es fácil ver que cada cuadro simétrico reflexivo se puede obtener de esta manera. Resulta que

⊢_{{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^*,$

donde la traducción conmuta con conectivos proposicionales y se define para operadores modales por $\phi^*$

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

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

Aquí, denota la modalidad universal de , y y respectivamente denotan las modalidades hacia adelante y hacia atrás de IK5. $A$ $\mathrm{KTB}^U$ $\Box^+$ $\Box^-$

Referencia:

[1] Cheng-Chia Chen y I-Peng Lin, La complejidad de las teorías modales proposicionales y la complejidad de la consistencia de las teorías modales proposicionales , en: Proc. LFCS 1994 (Anil Nerode y Yu. V. Matiyasevich, eds.), LNCS 813, Springer, págs. 69–80, doi 10.1007 / 3-540-58140-5_8 .

Emil Jeřábek
fuente

Tal vez una pregunta tonta. Según tengo entendido, usted demostró que la consecuencia global en IK5 es al menos tan difícil como la consecuencia global en KTB ^ U. Dado que la satisfacción local es un caso especial de un problema de consecuencia global, ¿cómo obtenemos dureza?

Bartosz Bednarczyk

No, probé que el teorema (que es un caso especial de consecuencia local y global) en IK5 es al menos tan difícil como el teorema en KTB ^ U. O, por lo general, la satisfacción en IK5 es tan difícil como la satisfacción en KTB ^ U. Dicho esto, en realidad no hace ninguna diferencia: la consecuencia local y la teorema tienen la misma complejidad en cualquier lógica modal por el teorema de deducción, y las consecuencias locales y globales tienen la misma complejidad en cualquier lógica con una modalidad universal definible (que IK5 tiene )

Emil Jeřábek

Emil Jeřábek, ¿conoce algún resultado de límite superior para IK5? ¿Diferentes técnicas que luego se traducen en GF2, que mencioné en mi publicación?

Bartosz Bednarczyk

Un argumento de filtración bastante sencillo muestra que cualquier fórmula satisfactoria tiene un modelo de tamaño

, lo que significa que se puede probar la satisfacción en NEXP. No conozco una forma directa de cómo hacer que el algoritmo sea determinista.

2^{O (n)}

$2^{O(n)}$

Emil Jeřábek

La última pregunta. ¿Podría decirme si ese resultado también nos da algún límite en el problema de la satisfacción global (no estoy familiarizado con la teoría, es por eso que pregunto)? Es fácil reducir la satisfacción global a la satisfacción local si puede utilizar la modalidad universal, pero tal vez el límite superior para IK5 sea menor que Exp.

Bartosz Bednarczyk

Complejidad de la lógica modal IK5

Respuestas: