전산물리학:xorsat

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
전산물리학:xorsat [2026/10/14 11:47] – [XORSAT] admin전산물리학:xorsat [2026/10/14 15:53] (current) – [3-XORSAT의 예] admin
Line 6: Line 6:
 x_1 \oplus x_2 \oplus x_4 &=& 0\\ x_1 \oplus x_2 \oplus x_4 &=& 0\\
 x_2 \oplus x_4 \oplus x_3 &=& 0\\ x_2 \oplus x_4 \oplus x_3 &=& 0\\
-x_1 \oplus x_2 \oplus x_3 &=& 0.+x_1 \oplus x_2 \oplus x_3 &=& 1.
 \end{eqnarray*} \end{eqnarray*}
 이때 $M=3$, $N=4$로서 이때 $M=3$, $N=4$로서
Line 14: Line 14:
 1 & 1 & 1 & 0 1 & 1 & 1 & 0
 \end{pmatrix} \] \end{pmatrix} \]
-이고 $\underline{b} = (0,0,0)^\intercal$이다. 가우스 소거법을 사용하면 아래 식으로 바꾸어 쓸 수 있다:+이고 $\underline{b} = (0,0,1)^\intercal$이다. 가우스 소거법을 사용하면 아래 식으로 바꾸어 쓸 수 있다:
 \[\begin{pmatrix} \[\begin{pmatrix}
 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\
Line 24: Line 24:
 \end{pmatrix} \end{pmatrix}
 = \begin{pmatrix} = \begin{pmatrix}
-0 \\ 0 \\ 0+1 \\ 1 \\ 1
 \end{pmatrix}. \end{pmatrix}.
 \] \]
-대각선의 오른편에 있는 변수인 $x_4$의 값은 임의로 1로 지정하자. 그러면 $x_1=1$, $x_2=0$, 그리고 $x_3=1$로 결정되어 자명하지 않은 해를 하나 얻을 수 있다.+대각선의 오른편에 있는 변수인 $x_4$의 값은 임의로 1로 지정하자. 그러면 $x_1=0$, $x_2=1$, 그리고 $x_3=0$로 결정되어 자명하지 않은 해를 하나 얻을 수 있다. $x_4=0$으로 놓으면 $x_1=1$, $x_2=1$, $x_3=1$이라는 해를 얻는다.
  
 이처럼 가우스 소거법으로 풀 수 있으므로 다항 시간 문제(P)에 속한다. 이처럼 가우스 소거법으로 풀 수 있으므로 다항 시간 문제(P)에 속한다.
 +
 +만일 위 세 개의 방정식 말고도 $x_1 \oplus x_2 \oplus x_4 = 1$이라는 방정식이 추가되었다면 첫 방정식과 모순이므로 해가 존재할 수 없다.
  
 해의 집합을 $\mathcal{S}$, 그 크기를 $Z = |\mathcal{S}|$라 하자. 해의 집합에 균일한 측도(measure)를 부여하여 다음처럼 적을 수 있다. 해의 집합을 $\mathcal{S}$, 그 크기를 $Z = |\mathcal{S}|$라 하자. 해의 집합에 균일한 측도(measure)를 부여하여 다음처럼 적을 수 있다.
Line 35: Line 37:
 이때 $\partial a = \left( i_a(1), \ldots, i_a(k) \right)$이고 이때 $\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) \] \[ \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을 돌려주는 함수이다.+이며, $\mathbb{I}$는 명제가 참일 때 1, 거짓일 때 0을 돌려주는 함수이다. 위의 예에서는 $\partial 1 = (1,2,4)$, $\partial 2 = (2,3,4)$, 그리고 $\partial 3 = (1,2,3)$이다. $\mathcal{S} = \{(0,1,0,1), (1,1,1,0)\}$로서 $Z=2$이고, 그래서 $\mu$에 따르면 전체 $2^4=16$개의 가능성 중 이 두 개의 해만 $1/2$씩 확률을 나누어 갖는다. 
 + 
 +선형대수로부터 다음의 사실이 알려져 있다: 
 +  * $\operatorname{rank}\mathbb{H} = M$이어서 모든 행이 선형독립이라면, 방정식 $\mathbb{H}\underline{x} = \underline{b}$는 임의의 $\underline{b}$에 대해 해를 가진다. 위의 예에서 $\operatorname{rank}\mathbb{H} = M = 3$인데, 실제로 $\underline{b}$를 어떻게 놓든 답을 구할 수 있다. 
 +  * $\operatorname{rank}\mathbb{H}<M$이라고 하자. 그러면 $\underline{b}$가 $\mathbb{H}$의 상(image) 안에 있을 때에, 그리고 그때에만 해가 존재한다. '행렬을 곱하여 나올 수 있는 모든 벡터들의 집합'이라는 상의 정의로부터 이 사실은 자명하다. 
 + 
 +방정식 $\mathbb{H} \underline{x} = \underline{b}$에 해가 존재한다면(표기를 간편하게 하기 위해 $\bmod 2$는 앞으로 생략한다), $Z = 2^{N-\operatorname{rank}\mathbb{H}}$이다. 위의 예에서 $N=4$와 $\operatorname{rank}\mathbb{H} = M = 3$이므로 실제로 해가 두 개 존재했다. 
 + 
 +  *$\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}$에 대해 같은 수의 해를 가진다. 앞의 예에 해당하는 동차 방정식을 풀면 $\mathcal{S}_0 = \{(1,0,1,1), (0,0,0,0)\}$이므로 (동차 방정식은 언제나 $\underline{0}$을 해로 가진다) 이 관계들을 쉽게 확인할 수 있다. 
 +  * 반면 $Z_0 > 2^{N-M}$이라면, 원래의 방정식은 모든 가능한 $\underline{b}$ 중에서 $2^{N-M}/Z_0$의 비율에 대해서만 충족 가능하다. 말하자면 위의 예를 아래처럼 바꾸었을 때, $x_4$와 함께 $x_3$의 값까지 결정되지 않으므로 해는 $Z_0=4$개가 나와서 $2^{N-M}=2$보다 많다. $\underline{b}$의 세 번째 원소가 1이라면 해가 존재하지 않으므로($0 \neq 1$), 모든 가능한 $\underline{b}$ 중 절반에 대해서만 해가 존재한다. 
 +\[\mathbb{H} = \begin{pmatrix} 
 +1 & 0 & 0 & 1\\ 
 +0 & 1 & 0 & 0\\ 
 +0 & 0 & 0 & 0 
 +\end{pmatrix}. 
 +\] 
 + 
 +====3-XORSAT의 예==== 
 +$N=M=6$인 경우이다: 
 +\[ \mathbb{H} = \begin{pmatrix} 
 +0 & 1 & 0 & 1 & 1 & 0\\ 
 +1 & 0 & 0 & 1 & 0 & 1\\ 
 +0 & 1 & 0 & 0 & 1 & 1\\ 
 +1 & 0 & 1 & 0 & 0 & 1\\ 
 +0 & 1 & 0 & 1 & 0 & 1\\ 
 +1 & 0 & 1 & 0 & 1 & 0 
 +\end{pmatrix}. 
 +\] 
 +가우스 소거법을 시행하면 다음을 얻는다: 
 +\[ \begin{pmatrix} 
 +1 & 0 & 0 & 0 & 0 & 0\\ 
 +0 & 1 & 0 & 0 & 0 & 0\\ 
 +0 & 0 & 1 & 0 & 0 & 1\\ 
 +0 & 0 & 0 & 1 & 0 & 1\\ 
 +0 & 0 & 0 & 0 & 1 & 1\\ 
 +0 & 0 & 0 & 0 & 0 & 0\\ 
 +\end{pmatrix}. 
 +\] 
 +따라서 $\operatorname{rank}\mathbb{H} =5$이고 $\mathcal{S}_0 = \{(0,0,1,1,1,1), (0,0,0,0,0,0)\}$로서 동차 방정식에 $Z_0=2$개의 해가 존재한다. 이는 $\mathbb{H} \underline{x} = \underline{b}$의 방정식에서 $b_6=0$이면 해가 존재하고 $b_6=1$이면 해가 존재하지 않는다는 사실과 부합한다. 
 + 
 +위 문제에 해당하는 [[수학:인자_그래프|인자 그래프]]를 그려보면 다음과 같다. 
  
-선형대수로부터 다음의 사실이 잘 알려져 있다: 
-  - $\mathbb{H}$가 계수(rank) $M$을 가져서 모든 행이 선형독립이라면, 방정식 $\mathbb{H}\underline{x} = \underline{b}$는 임의의 $\underline{b}$에 대해 해를 가진다. 
-  - $\operatorname{rank}(A)<M$이라고 하자. 그러면 $\underline{b}$가 $\mathbb{H}$의 상(image) 안에 있을 때에, 그리고 그때에만 해가 존재한다. 
  
  
  • 전산물리학/xorsat.1791946035.txt.gz
  • Last modified: 2026/10/14 11:47
  • by admin