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 ...
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
Related Tags
linear-algebra × 251algorithms × 93
matrices × 54
optimization × 31
linear-programming × 23
complexity-theory × 21
time-complexity × 19
computational-geometry × 17
machine-learning × 14
graphs × 12
sparse-matrices × 9
algorithm-analysis × 8
reference-request × 8
numerical-algorithms × 8
computer-vision × 7
coding-theory × 7
randomized-algorithms × 6
quantum-computing × 6
integer-programming × 6
numerical-analysis × 6
dynamic-programming × 5
combinatorics × 5
approximation × 5
image-processing × 5
boolean-algebra × 5