Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$.

Is it easier to check satisfiability of the system without finding a specific solution $x$, in terms of time complexity? (A solution can be found in matrix multiplication time.)

  • $\begingroup$ I changed GL(2) to GF(2). I assumed you did not actually mean the general linear group of degree 2 $\endgroup$ Jun 28, 2016 at 7:51
  • 3
    $\begingroup$ By doing a binary search on x, it can be easier at most by a factor of 2n. $\endgroup$ Jun 29, 2016 at 4:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.