Next: Previous Work
Up: A Scalable, Loadable Custom
Previous: Introduction
Definitions
A k-SAT formula is a Boolean expression in conjunctive normal
form.
 |
(1) |
In this case, n=3, m=4, and k=3.
For
,
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
 |
(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: Previous Work
Up: A Scalable, Loadable Custom
Previous: Introduction
2000-04-07