<p>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)$.</p>

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

CC BY-SA 3.0
2016-06-28T07:51:32.927Z
I changed GL(2) to GF(2). I assumed you did not actually mean the [general linear group of degree 2](https://en.wikipedia.org/wiki/General_linear_group)
Sasho Nikolov
CC BY-SA 3.0
2016-06-29T04:45:09.647Z
By doing a binary search on x, it can be easier at most by a factor of 2n.
Joshua Grochow
<cc.complexity-theory><time-complexity><linear-algebra>
Testing for satisfiability of a system of linear equations over GF(2)
user1387682
# Testing for satisfiability of a system of linear equations over GF(2)

(Asked by: username_0 on 2016-06-27)

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

**Tags:** cc.complexity-theory, time-complexity, linear-algebra
> **Comments:**
> **username_1**: I changed GL(2) to GF(2). I assumed you did not actually mean the [general linear group of degree 2](https://en.wikipedia.org/wiki/General_linear_group)  
> **username_2**: By doing a binary search on x, it can be easier at most by a factor of 2n.  

---

## 0 answers

