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$ – Sasho Nikolov Jun 28 '16 at 7:51
  • 3
    $\begingroup$ By doing a binary search on x, it can be easier at most by a factor of 2n. $\endgroup$ – Joshua Grochow Jun 29 '16 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.