Schaefer's theorem

Encyclopedia : S : SC : SCH : Schaefer's theorem

---

In computational complexity theory, a branch of computer science, Schaefer's theorem states necessary and sufficient conditions under which a set O of Boolean operators generate polynomial-time or NP-complete problems when some of the operators of O are applied to some of the propositional variables. In particular, it identifies six classes of sets of Boolean operators that generate problems lying in P, while all other classes generate NP-complete problems.

In particular, a set of Boolean operators O, when applied to a set of variables, produces instances that are always polynomial if any one of the following conditions holds for the operators of O:

1. all such operators result in [true] when all its arguments are [true];
2. all such operators result in [true] when all its arguments are [false];
3. all such operators are equivalent to a set of binary clauses;
4. all such operators are equivalent to a set of Horn clauses;
5. all such operators are equivalent to a set of dual-Horn clauses;
6. all such operators are equivalent to a set of affine formulae (e.g., [x_1 \oplus \cdots \oplus x_n = true]).

If O is a set of operators satisfying one of these conditions, the problem of establishing the propositional satisfiability of a formula obtained by applying some of these operators to some of the variables lies in P. On the other hand, if a class of such operators does not satisfy any of these conditions, the problem of satisfiability for formulae obtained by applying these operators to some of the variables is NP-complete.

References

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?