12
votes
6answers
1k views

SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
0
votes
1answer
240 views

Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...