HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Common method for solving satisfiability problems which lie in P

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
solvingmethodsatisfiabilityforwhichproblemscommonlie

Problem

I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete. However, all of the algorithms I know for them use specific techniques unique to that type of problem- e.g. unit propagation for Hornsat, linear algebraic techniques mod 2 for XORSAT, and various other techniques for 2-sat. Is there one general polytime algorithm which works for all of these problems in P? Thanks.

Solution

Schaefer's dichotomy theorem is proved by dividing CSPs into two types: those that can be reduced to one of a few specific problems in P, and the other to which SAT can be reduced (and so are NP-complete). Specifically, every CSP of the former type is either trivial (always satisfied by the constant 0 or the constant 1 assignment), can be reduced to 2SAT, can be reduced to HORN-SAT, or can be reduced to XOR-SAT. These are the only algorithms you need to solve these CSPs. There is no one single algorithm – there is a finite list of algorithms.

Context

StackExchange Computer Science Q#37637, answer score: 7

Revisions (0)

No revisions yet.