전산물리학: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 15:45] – [3-XORSAT의 예] admin전산물리학:xorsat [2026/10/14 15:53] (current) – [3-XORSAT의 예] admin
Line 43: Line 43:
   * $\operatorname{rank}\mathbb{H}<M$이라고 하자. 그러면 $\underline{b}$가 $\mathbb{H}$의 상(image) 안에 있을 때에, 그리고 그때에만 해가 존재한다. '행렬을 곱하여 나올 수 있는 모든 벡터들의 집합'이라는 상의 정의로부터 이 사실은 자명하다.   * $\operatorname{rank}\mathbb{H}<M$이라고 하자. 그러면 $\underline{b}$가 $\mathbb{H}$의 상(image) 안에 있을 때에, 그리고 그때에만 해가 존재한다. '행렬을 곱하여 나올 수 있는 모든 벡터들의 집합'이라는 상의 정의로부터 이 사실은 자명하다.
  
-방정식 $\mathbb{H} \underline{x} = \underline{b}$에 해가 존재한다면, $Z = 2^{N-\operatorname{rank}\mathbb{H}}$이다. 위의 예에서 $N=4$와 $\operatorname{rank}\mathbb{H} = M = 3$이므로 실제로 해가 두 개 존재했다.+방정식 $\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}$을 해로 가진다) 이 관계들을 쉽게 확인할 수 있다.   *$\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}$을 해로 가진다) 이 관계들을 쉽게 확인할 수 있다.
Line 55: Line 55:
  
 ====3-XORSAT의 예==== ====3-XORSAT의 예====
-$N=M=6$인 경우이다.+$N=M=6$인 경우이다:
 \[ \mathbb{H} = \begin{pmatrix} \[ \mathbb{H} = \begin{pmatrix}
 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 1 & 0\\
Line 63: Line 63:
 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1\\
 1 & 0 & 1 & 0 & 1 & 0 1 & 0 & 1 & 0 & 1 & 0
-\end{pmatrix}+\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$이면 해가 존재하지 않는다는 사실과 부합한다.+가우스 소거법을 시행하면 다음을 얻는다: 
 +\[ \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$이면 해가 존재하지 않는다는 사실과 부합한다. 
 + 
 +위 문제에 해당하는 [[수학:인자_그래프|인자 그래프]]를 그려보면 다음과 같다. 
 + 
  
  
  • 전산물리학/xorsat.1791960322.txt.gz
  • Last modified: 2026/10/14 15:45
  • by admin