$\mathbb{H}$가 $M\times N$ 행렬로서 각각의 원소는 0 또는 1이라고 하자. $\underline{b}$는 0 또는 1을 원소로 가지는 $M$차원 벡터이다. $\mathbb{H} \underline{x} = \underline{b} \bmod 2$를 풀었을 때 $N$차원 벡터인 해 $\underline{x}$의 존재 여부, 혹은 해의 개수에 관심이 있다. $\mathbb{H}$의 각 행이 정확히 $k$개의 1을 포함하면 $k$-XORSAT이라고 불린다.

예를 들어 아래의 XORSAT은 충족 가능하다. \begin{eqnarray*} x_1 \oplus x_2 \oplus x_4 &=& 0\\ x_2 \oplus x_4 \oplus x_3 &=& 0\\ x_1 \oplus x_2 \oplus x_3 &=& 0. \end{eqnarray*} 이때 $M=3$, $N=4$로서 \[ \mathbb{H} = \begin{pmatrix} 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix} \] 이고 $\underline{b} = (0,0,0)^\intercal$이다. 가우스 소거법을 사용하면 아래 식으로 바꾸어 쓸 수 있다: \[\begin{pmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}. \] 대각선의 오른편에 있는 변수인 $x_4$의 값은 임의로 1로 지정하자. 그러면 $x_1=1$, $x_2=0$, 그리고 $x_3=1$로 결정되어 자명하지 않은 해를 하나 얻을 수 있다.

이처럼 가우스 소거법으로 풀 수 있으므로 다항 시간 문제(P)에 속한다.

해의 집합을 $\mathcal{S}$, 그 크기를 $Z = |\mathcal{S}|$라 하자. 해의 집합에 균일한 측도(measure)를 부여하여 다음처럼 적을 수 있다. \[ \mu(\underline{x}) = \frac{1}{Z} \mathbb{I} \left(\mathbb{H}\underline{x} = \underline{b} \bmod 2\right) = \frac{1}{Z} \prod_{a=1}^M \psi_a (\underline{x}_{\partial a}).\] 이때 $\partial a = \left( i_a(1), \ldots, i_a(k) \right)$이고 \[ \psi_a (\underline{x}_{\partial a}) = \mathbb{I} \left( x_{i_1(a)} \oplus \ldots \oplus x_{i_k(a)} = b_a \right) \] 이며, $\mathbb{I}$는 명제가 참일 때 1, 거짓일 때 0을 돌려주는 함수이다.

선형대수로부터 다음의 사실이 알려져 있다:

• $\operatorname{rank}\mathbb{H} = M$이어서 모든 행이 선형독립이라면, 방정식 $\mathbb{H}\underline{x} = \underline{b}$는 임의의 $\underline{b}$에 대해 해를 가진다.
• $\operatorname{rank}\mathbb{H}<M$이라고 하자. 그러면 $\underline{b}$가 $\mathbb{H}$의 상(image) 안에 있을 때에, 그리고 그때에만 해가 존재한다.

방정식 $\mathbb{H} \underline{x} = \underline{b}$에 해가 존재한다면, $Z = 2^{N-\operatorname{rank}\mathbb{H}}$이다.

• $\mathbb{H}\underline{x} = \underline{0}$을 동차(homogeneous) 방정식이라 하고 그 해의 집합을 $\mathcal{S}_0$라고 하자. $\mathbb{H} \underline{x} = \underline{b}$의 특수해 $\underline{x}_\ast$가 있을 때, $\mathcal{S} = \underline{x}_\ast + \mathcal{S}_0$이다. 달리 말해서, 동차 방정식 $\mathbb{H}\underline{x} = \underline{0}$를 만족하는 해의 수가 $Z_0 = 2^{N-M}$이라면, 원래의 방정식 $\mathbb{H} \underline{x} = \underline{b}$은 임의의 $\underline{b}$에 대해 같은 수의 해를 가진다.
• 반면 $Z_0 > 2^{N-M}$이라면, 원래의 비동차 방정식은 모든 가능한 $\underline{b}$ 중에서 $2^{N-M}/Z_0$의 비율에 대해서만 충족 가능하다.

• https://en.wikipedia.org/wiki/XOR-SAT
• M. Mézard and A. Montanari, Information, Physics, and Computation (2009, Oxford University Press).