Skip to main content
clarified after looking at Andrea's answer
Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank of a generating matrix for this space (the number is $2^r$ for rank $r$). TheThis rank can be figured out by a standard linear algebra algorithm, so the counting problem is in polynomial time.

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank (the number is $2^r$ for rank $r$. The rank can be figured out by a standard linear algebra algorithm, so the counting problem is in polynomial time.

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank of a generating matrix for this space (the number is $2^r$ for rank $r$). This rank can be figured out by a standard linear algebra algorithm, so the counting problem is in polynomial time.

added 51 characters in body
Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank (the number is $2^r$ for rank $r$. The rank can be figured out by a standard linear algebra algorithm, so the counting problem is in polynomial time.

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank (the number is $2^r$ for rank $r$. The rank can be figured out by a standard linear algebra algorithm.

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank (the number is $2^r$ for rank $r$. The rank can be figured out by a standard linear algebra algorithm, so the counting problem is in polynomial time.

Source Link
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

The solutions for XOR-SAT form an affine subspace of the vector space GF(2)$^n$. You can see this by realizing that if you add three solutions together, you get another solution. The counting problem for XOR-SAT is then that of deciding how many points are in this affine space over GF(2). This is trivial if you know the rank (the number is $2^r$ for rank $r$. The rank can be figured out by a standard linear algebra algorithm.