Сложность однооборотного СМТ

Я ищу сложности выполнимости формулы или формулы где - формула вида: Где - постоянная в , а область переменных также равна . $\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$

ϕ := ϕ \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}$

На самом деле это либо либо . Это упрощает сложность? $y_i$ $0$ $1$

Весь ответ со ссылками будет с радостью принят.

Спасибо

cc.complexity-theory reference-request lo.logic wece
источник

Если phi был Boolean, то вы находитесь на втором уровне полиномиальной иерархии, потому что я могу решить эту проблему с помощью недетерминированной машины Тьюринга с использованием решателя SAT в качестве оракула. Разве здесь не будут работать те же рассуждения?

Миколас

Как указано в вопросе, это кажется даже неразрешимым, так как оно включает в себя 10-ю проблему Гильберта en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

Magnus Find

@MagnusFind Спасибо, вы правы. Но на самом деле у меня нет умножения (отредактировано, извините).

wece

@ Миколас, под вторым уровнем ты имеешь в виду или ? В не очень знакомы с полиномиальной иерархии извините.

Π_{2}

$\Pi_2$

Σ_{2}

$\Sigma_2$

13:30

У вас есть другие свободные переменные, кроме тех, которые определены количественно? Если это так, вы должны уточнить это тоже. Между прочим, простое наблюдение, по-видимому, заключается в том, что для третьего уровня полиномиальной иерархии это, по крайней мере, трудно, даже если принять количественные переменные равными и .

0

$0$

1

$1$

Каве

Ответы:

Редди и Лавленд с довольно определенной точностью ответили на вопрос об истине в арифметике Пресбургера с ограниченным чередованием кванторов:

CR Reddy и DW Loveland: арифметика Пресбургера с чередованием ограниченного квантификатора .

Бумага может быть найдена здесь (извините за уродливую ссылку). Их основной результат заключается в следующем:

Членство в (где - количество чередований кванторов) длины может быть определено в пространстве и в (детерминистском) времени Где и - постоянные. $\mathrm{PA}(m)$ $m$ $n$
$2^{d n^{m + 4}}$ $2^{dn^{m+4}}$ $2^{2^{e n^{m + 4}}}$ $2^{2^{en^{m+4}}}$ $d$ $e$

Принимая , это, по-видимому, дает по крайней мере верхнюю границу того, что вы хотите, и я подозреваю, что это не так уж сложно, поскольку у вас есть почти полные формулы атома Пресбургера "в корне". $m=2$

Коди
источник

Достаточно одного чередования в арифметике Пресбургера, чтобы получить экспоненциальные нижние оценки, точнее формул, как в вопросе с и не являющимся фиксированным, достаточно ( Grädel 1989 ). $m=1$ $n$

Сильвен
источник

Я не знаю ссылок на квантифицированный фрагмент, но ваша проблема не такая, как выбор хорошо изученных фрагментов арифметики Пресбургера, потому что у вас есть единичные коэффициенты.

В приведенной ниже статье Пратта рассматривается случай, когда ограничения имеют вид , где и - переменные, а - натуральное число. Он показывает, что проблема принятия решения о том, может ли соединение таких ограничений быть эффективно выполнено с использованием графового алгоритма. $x + c < y$ $x$ $y$ $c$

Две простые теории, комбинация которых сложна. Пратт, 1977.

Этот фрагмент также называется разностной логикой и на короткое время, к сожалению, называется разделительной логикой (поскольку и разделены константой). В следующей статье дается практический взгляд на решение проблемы без фрагмента задачи. $x$ $y$

Определение формул логики разделения по SAT и постепенному устранению отрицательного цикла. Чао Ванг, Франьо Иванчич, Малай Ганаи, Аарти Гупта, 2005.

В настоящее время ваш вопрос разрешает только коэффициенты и . Если вы также разрешите в качестве коэффициента, то соединения ограничений, которые вы получите, называются восьмиугольниками в литературе по анализу программ. Соединения и дизъюнкции ограничений образуют логику переменных второго модуля на неравенство (UTVPI) . Введение в следующей статье обзоров алгоритмов для определения выполнимости соединений без количественных ограничений UTVPI. $0$ $1$ $-1$

Эффективная процедура принятия решений для ограничений UTVPI. Шувенду К. Лахири и Маданлал Мусувати, 2005.

Мы все еще в очень ограниченном фрагменте. Распространение на конъюнкции переменных линейных неравенств с единичными коэффициентами называется октаэдром . Это настолько естественное продолжение, что я ожидаю, что оно было изучено в литературе по математическому программированию и оптимизации, но я сам не знаю эту литературу. В приведенной ниже статье дается процедура для определения выполнимости таких ограничений. Обратите внимание, что мы все еще в свободном фрагменте квантора. $n$ $\mathcal{O}(3^n)$

Абстрактная область октаэдра. Роберт Кларисо и Хорди Кортаделла, 2004.

Для случая чередования ограниченных квантификаторов я не знаю лучших результатов, чем результаты Редди и Лавленда, но, возможно, эксперт может указать вам правильное направление.

Виджай Д
источник