• English only

# Differences

This shows you the differences between two versions of the page.

sav08:dpll_algorithm_for_sat [2013/04/17 17:34]
vkuncak
sav08:dpll_algorithm_for_sat [2015/04/21 17:30] (current)
Line 90: Line 90:

**Decision step** (picking variable value): from proofs for **Decision step** (picking variable value): from proofs for
-$+\begin{equation*} S' \cup \{p\} \vdash {\it false} S' \cup \{p\} \vdash {\it false} -$ +\end{equation*}
-$+\begin{equation*} S' \cup \{\lnot p\} \vdash {\it false} S' \cup \{\lnot p\} \vdash {\it false} -$+\end{equation*}
we would like to construct the proof for we would like to construct the proof for
-$+\begin{equation*} S' \vdash {\it false} S' \vdash {\it false} -$+\end{equation*}
From From
-$+\begin{equation*} S' \cup \{p\} \vdash {\it false} S' \cup \{p\} \vdash {\it false} -$+\end{equation*}
derive proof tree for derive proof tree for
-$+\begin{equation*} S' \vdash \lnot p S' \vdash \lnot p -$+\end{equation*}
and from and from
-$+\begin{equation*} S' \cup \{\lnot p\} \vdash {\it false} S' \cup \{\lnot p\} \vdash {\it false} -$+\end{equation*}
derive proof tree for derive proof tree for
-$+\begin{equation*} S' \vdash p S' \vdash p -$+\end{equation*}
Then combine these two trees with resolution on $\{p\}$ and $\{\lnot p\}$ to get ${\it false}$. Then combine these two trees with resolution on $\{p\}$ and $\{\lnot p\}$ to get ${\it false}$.

Line 127: Line 127:
Theorem: for some formulas, shortest resolution proofs are exponential. Theorem: for some formulas, shortest resolution proofs are exponential.

-This does not contradict P vs NP question, because there may be "​better"​ proof systems than resolution.+This does not contradict ​that P vs NP question ​is open, because there may be "​better"​ proof systems than resolution.

Lower bounds for both resolution and a stronger system are shown here by proving that interpolants can be exponential,​ and that interpolants are polynomial in proof size (see [[Interpolants from Resolution Proofs]]): Lower bounds for both resolution and a stronger system are shown here by proving that interpolants can be exponential,​ and that interpolants are polynomial in proof size (see [[Interpolants from Resolution Proofs]]):
* Pavel Pudlák: [[http://​citeseer.ist.psu.edu/​36219.html|Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations]]   * Pavel Pudlák: [[http://​citeseer.ist.psu.edu/​36219.html|Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations]]