All reports by Author Lefteris Kirousis:

__
TR00-082
| 17th August 2000
__

Lefteris Kirousis, Phokion G. Kolaitis#### The Complexity of Minimal Satisfiability Problems

Revisions: 2

Lefteris Kirousis, Phokion G. Kolaitis

A dichotomy theorem for a class of decision problems is

a result asserting that certain problems in the class

are solvable in polynomial time, while the rest are NP-complete.

The first remarkable such dichotomy theorem was proved by

T.J. Schaefer in 1978. It concerns the ...
more >>>