3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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
    Commented 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$
    – Joshua Grochow
    Commented Jun 29, 2016 at 4:45

0

Reset to default

Your Answer

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