New answers tagged linear-algebra
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 ...
- 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.♦
- 154k
Top 50 recent answers are included