Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/StackCSTheory/status/748195540534460416
changed GL to GF, fixed some grammatical mistakes, and tried to improve clarity
Source Link
Sasho Nikolov
Sasho Nikolov
  • 18.3k
  • 2
  • 68
  • 117

Testing for existence tosatisfiability of a system of linear equations over GF(2)

Consider a system linear equationequations in $GL(2)$

$A*X =b (mod 2)$

Were$x$, $Ax =b$, where A is matrix $n*n$an $n\times n$ matrix, and b$b$ is a column vector., and all values inoperations are over $GL(2)$$GF(2)$.

Is it easier to check satisfactionsatisfiability of the system without finding a specific solution to them$x$, in termterms of time complexity? (that require $O(n^\omega)$ running time which is the multiplyingA solution can be found in matrix complexity)multiplication time.)

Testing for existence to system of linear equations

Consider a system linear equation in $GL(2)$

$A*X =b (mod 2)$

Were A is matrix $n*n$ , and b is a column vector. all values in $GL(2)$

Is it easier to check satisfaction of the system without finding a specific solution to them, in term of time complexity? (that require $O(n^\omega)$ running time which is the multiplying matrix complexity).

Testing for satisfiability of a system of linear equations over GF(2)

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

Source Link
user1387682
user1387682
  • 271
  • 1
  • 6

Testing for existence to system of linear equations

Consider a system linear equation in $GL(2)$

$A*X =b (mod 2)$

Were A is matrix $n*n$ , and b is a column vector. all values in $GL(2)$

Is it easier to check satisfaction of the system without finding a specific solution to them, in term of time complexity? (that require $O(n^\omega)$ running time which is the multiplying matrix complexity).