2-in-3-SAT vs. Gaussian elimination

262 Views Asked by At

$\mathsf{P}\stackrel{?}{=}\mathsf{NP}$ is an open question currently. However monotone 2-in-3-SAT is an $\mathsf{NP}$-complete problem.

Further any 2-in-3 clause $(x\lor y\lor z)$ can be reduced to a modular equation $x+y+z\equiv 2 \pmod 3$. Then we can convert any problem in $\mathsf{NP}$ to a system of such formulas.

If it's possible to use Gaussian elimination (and why it should be impossible?) then it is possible to solve this in polynomial time which implies $\mathsf{P=NP}$.

But this was so simple, so trivial, that I don't even believe that this is possible and I'm correct. On the other hand simplicity of this doesn't allow me to see that something is wrong.

So, is there something I am missing or this really is so simple?