next up previous
Next: Previous Work Up: A Scalable, Loadable Custom Previous: Introduction

   
Definitions

A k-SAT formula is a Boolean expression in conjunctive normal form.

 \begin{displaymath}
(A+B+C)(\overline{A}+\overline{B})
(\overline{B}+\overline{C})
(\overline{A}+B+\overline{C})
\end{displaymath} (1)

In this case, n=3, m=4, and k=3. For $k \geq 3$, this class of problems is known to be NP-hard.

When the partial truth assignment [A=1, C=1] is applied to formula 1, it becomes

 \begin{displaymath}
(\textbf{T}+B+\textbf{T})
(\textbf{F}+\overline{B})
(\overline{B}+\textbf{F})
(\textbf{F}+B+\textbf{F})
\end{displaymath} (3)

and causes transitive implications B=0 and B=1. Since this is a contradiction, the partial truth assignment [A=1, C=1] cannot be part of any satisfying assignment.


next up previous
Next: Previous Work Up: A Scalable, Loadable Custom Previous: Introduction

2000-04-07