Complexidade da lógica modal IK5

Qual é a complexidade do problema de satisfação local para a lógica modal ? Aqui, denotamos por a lógica modal sobre quadros euclidianos estendidos com modalidade inversa. Você poderia fornecer alguma referência? Está em ? $\mathit{IK5}$ $IK5$ $NP$

O que eu sei sobre o tópico?

É fácil ver que o está no , já que há uma redução para (o fragmento guardado de duas variáveis da lógica de primeira ordem) - consulte Decidindo lógicas gramaticais regulares com inversão através da lógica de primeira ordem . $IK5$ $ExpTime$ $GF^2$

Por outro lado, o comum é completo. $K5$ $NP$

Podemos escrever uma fórmula equisatisfatável em (o fragmento de uma variável da lógica de primeira ordem), porque os modelos podem ser divididos em três partes: (1) mundo inicial , (2) sucessores de (3) sucessores dos sucessores de . O exemplo de redução para uma lógica ainda mais difícil ( com modalidades classificadas) é descrito em Uma nota sobre a complexidade do problema de satisfação para lógicas modais classificadas . No entanto, na presença de uma modalidade inversa, não podemos fazer o mesmo truque - a breve idéia é que mundos inversos podem exigir o número diferente de sucessores. $FO^1$ $w$ $w$ $w$ $K5$

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

A lógica é EXP-completa. Uma maneira de provar o limite inferior é observar que a lógica KTB aumentada com a modalidade universal, ou mesmo apenas a relação global de conseqüências da KTB, é EXP-completa (Chen e Lin [1]; observe que eles indicam KTB como B).

Observe que um quadro IK5 conectado é um único ponto irreflexivo ou consiste em um cluster reflexivo junto com um conjunto (possivelmente vazio) de pontos irreflexivos, cada um dos quais vê (em ) um subconjunto não vazio de . Assim, $(W,R,R^{-1})$ $C$ $I$ $R$ $C$ é uma relação simétrica em ; se todo elemento de é visto por um elemento de , também é reflexivo. Por outro lado, é fácil ver que toda estrutura simétrica reflexiva pode ser obtida dessa maneira. Segue que

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

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

onde a tradução comuta com conectivos proposicionais e é definida para operadores modais por $\phi^*$

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

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

Aqui, denota a modalidade universal de , e e denotam respectivamente as modalidades de avanço e retrocesso de IK5. $A$ $\mathrm{KTB}^U$ $\Box^+$ $\Box^-$

Referência:

[1] Cheng-Chia Chen e I-Peng Lin, A complexidade das teorias modais proposicionais e a complexidade da consistência das teorias modais proposicionais , em: Proc. LFCS 1994 (Anil Nerode e Yu. V. Matiyasevich, orgs.), LNCS 813, Springer, pp. 69-80, doi 10.1007 / 3-540-58140-5_8 .

Emil Jeřábek
fonte

Talvez uma pergunta boba. Tanto quanto eu entendo, você provou que a consequência global em IK5 é pelo menos tão difícil quanto a consequência global em KTB ^ U. Como a satisfação local é um caso especial de problema de conseqüência global, como obtemos dureza para isso?

Bartosz Bednarczyk

Não, eu provei que a teorema de idade (que é um caso especial de conseqüência local e global) em IK5 é pelo menos tão difícil quanto a teorema de idade em KTB ^ U. Ou, duplamente, a satisfação em IK5 é tão difícil quanto a satisfação em KTB ^ U. Dito isto, isso realmente não faz nenhuma diferença: conseqüência local e teorematismo têm a mesma complexidade em qualquer lógica modal pelo teorema da dedução, e conseqüência local e global têm a mesma complexidade em qualquer lógica com uma modalidade universal definível (que IK5 possui )

Emil Jerabek

Emil Jeřábek, você está ciente de algum resultado de limite superior para o IK5? Diferentes técnicas, em seguida, traduzindo para GF2, que eu mencionei no meu post?

Bartosz Bednarczyk

2^{O (n)}

$2^{O(n)}$

A última questão. Você poderia me dizer se esse resultado também nos dá algum problema com o problema de satisfação global (não estou familiarizado com o teorema, por isso estou perguntando)? É fácil reduzir a satisfação global à satisfação local se você puder usar a modalidade universal, mas talvez o limite superior do IK5 seja menor que o Exp.

Bartosz Bednarczyk

Complexidade da lógica modal IK5

Respostas: