Complexidade de uma alternância SMT

Eu estou olhando para a complexidade de satisfazibilidade de uma fórmula ou de uma fórmula onde é a fórmula da forma: $\forall y_1, \dots,y_n, \exists x_1,\dots,x_m, \phi$ $\exists x_1,\dots,x_m \forall y_1, \dots,y_n,\phi$ $\phi$ onde é a constante em , e o domínio de variáveis também é .

ϕ := ϕ \land ϕ | \neg ϕ | ϕ \to ϕ | ψ

$\phi:= \phi \wedge\phi ~| ~\neg \phi ~| ~ \phi\to \phi~| ~\psi$

ψ := t > t | t = t

$\psi := t>t~| ~t=t$

t := t + t | x_{i} | y_{i} | c

$t:= t+t~| ~x_i~|~y_i ~| ~c$

c

$c$

N

$\mathbb{N}$

x_{i}, y_{i}

$x_i,y_i$

N

$\mathbb{N}$

Na verdade, a são ou ou . Isso simplifica a complexidade? $y_i$ $0$ $1$

Todas as respostas com referências serão aceitas com prazer.

obrigado

cc.complexity-theory reference-request lo.logic wece
fonte

Se phi era booleano, você está no segundo nível da hierarquia polinomial, porque eu posso resolver o problema por uma máquina de Turing não determinística, usando um solucionador SAT como um oráculo. O mesmo raciocínio não funcionaria aqui?

Mikolas

Como afirmado na questão parece ainda indecidível, já que inclui Hilberts 10 problema en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

Magnus Encontrar

@MagnusFind Obrigado, você está certo. Mas, na verdade, não tenho a multiplicação (editada, desculpe).

wece

@ Mikolas por segundo nível, você quer dizer

? Em não realmente familiarizado com a hierarquia polinomial desculpe.

Π_{2}

$\Pi_2$

Σ_{2}

$\Sigma_2$

wece

Você tem outras variáveis livres além daquelas quantificadas? Nesse caso, você deve esclarecer isso também. Aliás, uma observação fácil parece ser que isso é pelo menos difícil para o terceiro nível da hierarquia polinomial, mesmo se você considerar as variáveis quantificadas como

0

$0$

1

$1$

Kaveh

Respostas:

A questão da verdade na aritmética de Presburger com alternância de quantificador limitado foi respondida com bastante precisão por Reddy e Loveland:

CR Reddy e DW Loveland: aritmética de pré -burger com alternância de quantificador limitado .

O documento pode ser encontrado aqui (desculpe pelo feio link). O principal resultado é apresentado da seguinte forma:

A adesão em (onde $\mathrm{PA}(m)$ é o número de quantificador alternâncias) de comprimento pode ser decidido no espaço e no tempo (determinístico) onde e são constantes. $m$ $n$
$2^{d n^{m + 4}}$ $2^{dn^{m+4}}$ $2^{2^{e n^{m + 4}}}$ $2^{2^{en^{m+4}}}$ $d$ $e$

Tomando , isso parece dar pelo menos um limite superior ao que você deseja, e eu suspeito que não esteja longe de ser apertado, pois você tem quase todas as fórmulas atômicas do Presburger "na raiz". $m=2$

cody
fonte

Uma única alternância em Presburger aritmética é suficiente para obter limites inferiores exponenciais, mais precisamente fórmulas como na pergunta com e não são suficientes fixo ( GRADEL 1989 ). $m=1$ $n$

Sylvain
fonte

Não conheço referências para o fragmento quantificado, mas seu problema não é o mesmo que decidir fragmentos bem estudados da aritmética de Presburger, porque você tem coeficientes de unidade.

$x + c < y$ $x$ $y$ $c$

Duas teorias fáceis cuja combinação é difícil. Pratt, 1977.

$x$ $y$

Decidir fórmulas de lógica de separação por SAT e eliminação do ciclo negativo incremental. Chao Wang, Franjo Ivančić, malaio Ganai, Aarti Gupta, 2005.

$0$ $1$ $-1$

Um procedimento de decisão eficiente para restrições de UTVPI. Shuvendu K. Lahiri e Madanlal Musuvathi, 2005.

$n$ $\mathcal{O}(3^n)$

O domínio abstrato do octaedro. Robert Clarisó e Jordi Cortadella, 2004.

Para o caso de alternância de quantificadores limitados, não conheço melhores resultados do que os de Reddy e Loveland, mas talvez um especialista possa apontá-lo na direção certa.

Vijay D
fonte