3SAT Problem Solving

461 Views Asked by At

Lets say an integer constraint is a statement which relations of either: =, $\geq$ or $\leq$ and either side of the relation has have an expression consisting of variables and integers joined by + and -.

Problem (EQ) consists of a set of integer constrints over a collection of variables. Can each variable be assigned an integer value such that all integer constraints are satisfied? Prove 3SATd$\leq_p$EQ

1

There are 1 best solutions below

0
On BEST ANSWER

Each integer constraint can be written (after introducing some more variables) using clauses of the form $x + y = z$ and $x = \text{constant}$. At the bit level, $x+y=z$ can be written using "full adders": $x + y + z = w + 2 c$ where $x,y,z,w,c$ are single bits ($0$ or $1$). Full adders can be constructed using OR, AND and NOT gates, which correspond to 3SAT clauses.