In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem states necessary and sufficient conditions under which a finite set S of relations over the Boolean domain yields polynomial-time or NP-complete problems when the relations of S are used to constrain some of the propositional variables. It is called a dichotomy theorem because the complexity of the problem defined by S is either in P or NP-complete as opposed to one of the classes of intermediate complexity that is known to exist (assuming P ≠ NP) by Ladner's theorem.
Special cases of Schaefer's dichotomy theorem include the NP-completeness of SAT (the Boolean satisfiability problem) and its two popular variants 1-in-3 SAT and Not-All-Equal 3SAT (often denoted by NAE-3SAT). In fact, for these two variants of SAT, Schaefer's dichotomy theorem shows that their monotone versions (where negations of variables are not allowed) are also NP-complete.
Read more about Schaefer's Dichotomy Theorem: Original Presentation, Modern Presentation, Generalizations, Related Work
Famous quotes containing the words dichotomy and/or theorem:
“I am a Christian according to my conscience in belief, ... in purpose and wish;Mnot of course by the orthodox standard. But I am content, and have a feeling of trust and safety.
The Machiavellian mind and the merchant mind are at one in their simple faith in the power of segmental division to rule all—in the dichotomy of power and morals and of money and morals.”
—Marshall McLuhan (1911–1980)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)