11/17/2011

Boolean satisfyability is known as empty complete-- because given a set of boolean constraints its hard to get variable which satisfies these conditions.

In general 1 sat is east to solve, 2 sat is polynomial and 3 sat is empty complete.

Anuj