All Questions

In an answer here Dima Pasechnik showed that constraints of the form $x_i x_j + a_{ij}x_i + b_{ij}x_j + c_{ij}$ are efficiently solvable modulo $2$ using Groebner basis. In comments he suggested that ...

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 ...