New answers tagged

0 votes

Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}_2$?

No, unless P=NP. Cook-Levin showed SAT is an NP-complete problem. Solving a system of linear equations is a polynomial time problem. Also, Schaefer's Dichotomy Theorem says that SAT problems can ...
Geremia's user avatar
  • 146
3 votes

Can any SAT problem be converted to a system of linear equations over $\mathbf{Z}_2$?

Equivalence: Not every SAT instance can be expressed as a system of linear equations. For instance, $x_1 \lor x_2$ cannot be expressed as a system of linear equations. (Why not? Systems of linear ...
D.W.'s user avatar
  • 154k

Top 50 recent answers are included