\begin{slide}{CNF-SAT als FD-Constraint-Problem}

  \begin{itemize} \itemsep 2pt
  \item Universum $U=\{0,1\}$
  \item Funktion $N(x) := (1-x)$, 
  \item Relation $O(x_1,\ldots,x_k)=(x_1+\ldots+x_k\ge 1)$
  \end{itemize}
übersetze CNF $(p\vee \neg q)\wedge (q\vee r)$

in äquivalentes FD-Problem $O(p,N(q))\wedge O(q,r)$

\begin{itemize}\itemsep 2pt
\item FD-Constraint-Lösen ist wenigstens so schwer
  wie SAT-Lösen (also NP-vollständig)
\item Algorithmen sind auch ähnlich (zu DPLL), Unterschiede:
  \begin{itemize}
  \item SAT: CDCL 
  \item FD: Verfeinerung des Konzeptes \emph{Konflikt}
  \end{itemize}
\end{itemize}


\end{slide}
