owned this note
owned this note
Published
Linked with GitHub
![](https://i.imgur.com/38TiHGm.png)
Wpierw pokażemy przekształcenie kwantyfikatorów ogólnych na kwantyfikatory egzystencjonalne.
Rozważmy 3 przypadki
1. Kwantyfikatory ogólne są z prawej strony:
\begin{aligned} \exists x_1 \ldots \exists x_{n-2}\forall y_1 \forall y_2 \varphi\end{aligned}
\begin{aligned}\Updownarrow \end{aligned}
\begin{aligned}\exists x_1 \ldots \exists x_{n-2} \varphi(\vec{x}, 0, 1) \wedge \varphi(\vec{x}, 1, 0) \wedge \varphi(\vec{x}, 1, 1) \wedge \varphi(\vec{x}, 0, 0)\end{aligned}
Ponieważ takie ułożenie kwantyfikatorów ogólnych oznacza, że muszą istnieć wartościowania $x_1 \ldots x_{n-1}$ takie, że dla wszystkich kombinacji wartościowań $y_1, y_2$ formuła $\varphi$ jest spełniona.
2. Kwantyfikatory ogólne są z lewej strony:
\begin{aligned} \forall y_1 \forall y_2 \exists x_1 \ldots \exists x_{n-2} \varphi\end{aligned}
\begin{aligned}\Updownarrow \end{aligned}
\begin{aligned}(\exists x_1 \ldots \exists x_{n-2} \varphi(\vec{x}, 0, 1)) \wedge (\exists x_1' \ldots \exists x_{n-2}' \varphi(\vec{x'}, 1, 0)) \wedge \ldots\end{aligned}
Innymi słowy kiedy kwantyfikatory ogólne są z lewej strony, oznaczają one, że dla dowolnej kombinacji wartościowań $y_1, y_2$ muszą istnieć wartościowania $x_1 \ldots x_{n-2}$ (niekoniecznie takie same, stąd świeże zmienne przy kolejnych koniunkcjach) spełniające formułę $\varphi$.
3. Kwantyfikatory ogólne są w środku:
\begin{aligned}
\exists x_1 \ldots \exists x_i \forall y_1 \exists z_1 \ldots \exists z_j \forall y_2 \exists v_1 \ldots \exists v_k \varphi
\end{aligned}
W tym przypadku rozważamy kolejne fragmenty tej kolejności kwantyfikatorów wykorzystując wczesniej przedstawione przekształcenia, czyli:
* Zamieniamy $\exists x_1 \ldots \exists x_{j} \forall y_1$ na:
\begin{aligned}\exists x_1 \ldots \exists x_{n-2} ( \exists z_1 \ldots \exists z_j \forall y_2 \exists v_1 \ldots \exists v_k \varphi(\vec{x}, y_1=0) \wedge \exists z_1 \ldots \exists z_j \forall y_2 \exists v_1 \ldots \exists v_k \varphi(\vec{x}, y_1=1))\end{aligned}
* Następnie postepujemy analogicznie z $y_2$. Zauważmy, że $|x|$, $|z|$ i $|v|$ może wynosić 0, zatem zawsze używamy odpowiedniego przekształcenia (np. jeśli $|x| = 0$, to zamiast używać reguły 1, to na początek użyjemy 2 reguły do usunięcia $y_1$)
1. Taki algorytm przekształca dane wyrażenie logiczne w czasie wielomianowym. Po przekształceniu formuła zawiera wyłącznie kwantyfikatory egzystencjonalne, zatem możemy użyć generycznego algorytmu rozwiązującego problem $SAT$. Ostatecznie dostaliśmy algorytm działający w czasie $NP$.
2. Problem jest $NP$-zupełny - robimy trywialną redukcję
\begin{align} SAT \leq_p zad_{203} \end{align}
Problem $SAT$ możemy przekształcić do formuły z kwantyfikatorami egzystencjalnymi i nastepnie go rozwiązać $zad_{203}$, ponieważ obsługuje ono formuły do 2 kwantyfikatorów ogólnych, więc w szczególności takie gdzie nie ma żadnego.
Zatem problem jest $NP$-zupełny