0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .