카테고리 없음

[전산학특강] 전산학특강 - 11

7_JUN_7 2023. 10. 31. 03:44

 이분 그래프에서 완벽한 매칭이 존재하는지 결정하는 확률론적 알고리즘의 예

 

G = (U, V; E)가 에지 집합 E = {e1, e2, ..., em}를 가진 이분 그래프라고 하자.
K는 최대 반복 횟수입니다.
k = 1부터 K까지 다음을 수행합니다:
    E의 각 에지 e에 대해 {1, 2, ..., m} 집합에서 무작위로 x_e 값을 생성합니다.
    각 e = [i, j] ∈ E에 대해 a_ij 값을 x_e로 설정합니다.
    각 [i, j] ∈ E에 대해 a_ij 값을 0으로 설정합니다.
    만약 det A(G) ≠ 0이면 '예'를 반환합니다. [주석: G는 완벽한 매칭을 포함하고 있다.]
반복이 끝나면 '아니오'를 반환합니다.


주의: A는 G의 투트 행렬이 아닙니다.

이 알고리즘은 주어진 이분 그래프 G에서 완벽한 매칭이 존재하는지 확인하기 위한 확률론적 접근법을 사용합니다.

  1. 이분 그래프 G가 주어집니다. 이분 그래프는 두 개의 독립적인 정점 집합 U와 V와 이들을 연결하는 에지 집합 E로 구성됩니다.
  2. 알고리즘이 최대 K 번 반복됩니다.
  3. 각 반복에서, 에지 집합 E의 모든 에지에 대해 1부터 m까지의 값 중에서 무작위로 값을 선택하여 행렬 A의 해당 요소에 할당합니다.
  4. 행렬 A의 행렬식이 0이 아니면 그래프 G에는 완벽한 매칭이 있다고 결정됩니다.
  5. K번의 반복 동안 완벽한 매칭을 찾지 못하면, 알고리즘은 완벽한 매칭이 없다고 결정합니다.

이 알고리즘은 확률론적이므로 항상 올바른 답을 제공하지는 않지만, 충분한 반복 횟수 K와 적절한 초기 조건 하에서 높은 확률로 올바른 답을 찾을 수 있습니다. 마지막으로, 주어진 행렬 A는 투트 행렬이 아니라는 것을 명시하고 있습니다. 투트 행렬은 그래프의 매칭에 관련된 다른 유형의 행렬입니다.

 

p의 모든 항의 계수가 0이면,
p는 항상 0입니다.

G3 - 만약 모든 변수에 1을 할당하면,
행렬식은 완벽한 매칭이 있음에도 0이 됩니다!

 

  1. 첫 번째 문장은 어떤 다항식 p에 대해, 그 다항식의 모든 항의 계수가 0이라면, 해당 다항식은 항상 0의 값을 가진다는 것을 의미합니다.
  2. 그림에서 세 개의 이분 그래프 G1, G2, G3가 제시되었습니다. 이 그래프들은 각각 다른 연결 구조를 가지고 있습니다.
  3. 그 다음에 주어진 행렬들은 각 그래프의 연결 관계를 나타내는 행렬로 보입니다. 이 행렬의 요소 값들은 xij 형태로 표현되어 있으며, 각 xij는 해당 에지가 그래프에 존재하는지의 여부와 그 에지의 가중치를 나타낼 수 있습니다.
  4. det MGi는 i번째 그래프에 대한 행렬의 행렬식을 나타냅니다. 행렬식의 값이 0이 아니라면 그래프에 완벽한 매칭이 있다는 것을 의미합니다.
  5. 마지막으로, 주어진 텍스트는 G3에 대해 특별한 주의를 기울여 설명하고 있습니다. 모든 변수에 1의 값을 할당했을 때 행렬식의 값이 0이 되지만, 그래프 G3에는 완벽한 매칭이 존재한다는 것을 지적하고 있습니다. 이는 알고리즘이나 방법의 한계를 보여주는 예시로, 이분 그래프의 완벽한 매칭을 판별하는 데 있어서 단순히 행렬의 행렬식만으로는 부족할 수 있다는 것을 나타냅니다.

복잡성 이론은 일반적으로 '예/아니오' 문제들을 고려합니다: 이것은 원하는 출력의 특정 비트를 계산하는 어려움에 대한 검토입니다. '예/아니오' 문제들은 입력의 특성입니다: 답변이 '예'인 모든 입력의 집합을 가지고 있는 속성에 대해요. 특정 입력이 속성 T를 가지는지 확인하는 복잡성 대신에, 설명적 복잡성에서는 속성 T를 공식 언어로 얼마나 표현하기 어려운지 물어봅니다. 검사하기 어려운 속성이 표현하기 어려울 수 있다는 것은 타당합니다. 놀랍게도, 수학이 어떻게 물리적 세계를 흉내내는지입니다: 우리가 일차 논리를 사용할 때, 설명적 복잡성은 정확하게 중요한 복잡성 클래스를 포착합니다.

  1. 복잡성 이론: 컴퓨터 과학의 한 분야로, 알고리즘의 시간 및 공간 복잡성에 대한 연구를 포함합니다.
  2. '예/아니오' 문제: 문제의 해결이 '예' 또는 '아니오'로만 응답되는 경우를 가리킵니다. 예를 들면, "이 문제의 해결은 가능한가?"라는 질문이 있을 때, 답변은 '예' 또는 '아니오'일 것입니다.
  3. 설명적 복잡성: 문제나 데이터의 복잡성을 기술하는 데 필요한 정보의 양에 관한 연구입니다.
  4. 일차 논리: 수학과 철학에서 사용되는 논리체계 중 하나로, 객체와 그 객체 간의 관계를 표현하는 데 사용됩니다.
  5. 글에서는 설명적 복잡성과 일차 논리를 사용하여 문제의 복잡성을 어떻게 표현하는지에 대한 논의가 있습니다. 특히, 수학이 어떻게 실제 물리적 세계를 반영하는지에 대한 관점에서 놀라움을 표현하고 있습니다.

설명적 복잡성에서 우리는 입력을 유한 논리 구조로 볼 수 있습니다. 예를 들어, 바이너리 문자열 \( w = w_1 w_2 ... w_w \)는 \( A_w = \{ \{ 1, 2, ..., |w| \}, S^w, < \} \)로 코드화됩니다. 이것은 \( U = \{ 1, 2, ..., |w| \} \)의 우주로 구성되며 문자열 내의 비트 위치입니다. 단항 관계 \( S^w \)는 \( w \)의 \( i \)번째 비트가 1인 경우 \( S^w(i) \)가 유효하도록 정의됩니다. 그리고 \( < \)는 \( U \)상의 일반적인 전체 순서입니다.

그래프는 \( A_G = \{ \{ 1, 2, ..., v \}, E^G \} \)의 논리 구조이며, 여기서 그 우주는 꼭짓점의 집합이고 \( E^G \)는 바이너리 엣지 관계입니다. 그래프 문제는 단일 이항 관계로 구성된 어휘를 가진 유한 구조의 집합입니다. 마찬가지로, 우리는 어떤 복잡성 클래스 \( C \) 내의 문제 \( T \)를 일정한 어휘의 구조 집합으로 생각할 수 있습니다.

  1. 설명적 복잡성: 이론에서는 주어진 데이터나 문제의 복잡성을 기술하기 위해 필요한 정보의 양을 연구합니다.
  2. 바이너리 문자열: 0과 1로 구성된 문자열입니다. 여기서 �는 바이너리 문자열을 나타냅니다.
  3. 우주 (Universe): 주어진 컨텍스트나 집합 내의 모든 가능한 원소들의 집합을 의미합니다.
  4. 단항 관계: 하나의 인자만을 가진 관계를 의미합니다. 여기서 ��는 � 문자열 내의 특정 위치에 1이 있을 때만 참이 되는 관계를 나타냅니다.
  5. 그래프: 여기서 그래프는 꼭짓점 (vertices)와 엣지 (edges)로 구성된 수학적 구조를 의미합니다.
  6. 이항 관계: 두 개의 인자를 가진 관계를 의미합니다. 여기서는 그래프의 엣지 관계가 이에 해당합니다.

이 텍스트는 설명적 복잡성에서 유한 논리 구조의 형태로 문제나 데이터를 어떻게 표현하는지에 대한 기본 개념을 설명하고 있습니다.

 

expressibility(표현성)

 

 

첫 번째 순서 논리에서 우리는 우주 전체에 대해 양자화 할 수 있다는 것을 기억하세요. 예를 들어, 문자열이 1로 끝난다고 말할 수 있습니다. 다음 문장은 문자열 위치 x가 마지막 위치라는 것과 해당 위치의 비트가 1이라는 것을 주장함으로써 이를 수행합니다:
∃x∀y(y ≤ x ∧ S(x))

다른 예로, 우리는 모든 꼭짓점에서 떠나는 엣지가 정확히 두 개라는 것을 말할 수 있습니다:
∀x∃y∃z∀w(y ≠ z ∧ E(x,y) ∧ E(x,z) ∧ (E(x,w) → w=y ∨ w=z))

어떤 구조 A에 대해서, 우리는 'A |= φ'의 표기법을 사용하여 φ가 A에서 참이라는 것을 의미합니다.

  1. 첫 번째 순서 논리: 변수가 객체에만 연결될 수 있는 논리 체계입니다. 이 논리에서는 우주(또는 도메인)의 객체에 대해 주장하고 양자화할 수 있습니다.
  2. 문자열이 1로 끝남: 주어진 문자열의 마지막 비트가 1이라는 것을 표현하는 논리적 문장입니다. 여기서 S(x)는 x 위치의 비트가 1이라는 것을 나타냅니다.
  3. 떠나는 엣지가 두 개인 꼭짓점: 이 논리적 문장은 그래프의 모든 꼭짓점에서 떠나는 엣지가 정확히 두 개라는 것을 주장합니다. E(x,y)는 x 꼭짓점에서 y 꼭짓점으로의 엣지가 존재함을 나타냅니다.
  4. 논리적 참: 'A |= φ'는 구조 A에서 논리적 문장 φ가 참이라는 것을 나타냅니다.

이 텍스트는 첫 번째 순서 논리를 사용하여 다양한 문장이나 주장을 어떻게 표현하는지에 대한 예제를 제공하고 있습니다.

 

서술적 복잡도는 Ronald Fagin의 다음의 정리로 시작되었습니다. Fagin의 정리는 NP의 문제 집합이 두 번째 순서의 존재론적 논리로 기술될 수 있다고 말합니다. Fagin의 정리가 복잡도 클래스 NP를 순전히 논리적으로, 기계나 시간의 언급 없이 특성화한다는 것을 주목하세요.

정리 1: 구조 집합 T가 NP 내에 있다면, 그러한 두 번째 순서의 존재론적 공식 Φ가 존재하여 T = {A|A |= Φ}이다.

 

 

 

튜링 기계 없이 NP의 특성화
- 2차 존재문장(SOE)

NP는 SOE가 존재하는 구조 T의 집합이며, T는 A에서 s가 참인 구조 A의 집합입니다.

  • 서술적 복잡도: 컴퓨터 과학에서, 서술적 복잡도는 문제의 복잡도를 기술하기 위해 논리를 사용하는 연구 분야입니다.
  • NP: 복잡도 이론에서, NP는 비결정적 다항 시간에 속하는 결정 문제의 클래스입니다. 다시 말해, 주어진 해가 올바른지 다항 시간 내에 확인할 수 있는 문제의 집합입니다.
  • 두 번째 순서의 논리: 변수들이 객체 뿐만 아니라 객체의 집합에 대해서도 양자화될 수 있는 논리 체계입니다.
  • Fagin의 정리: 이 정리는 NP의 문제들이 두 번째 순서의 존재론적 논리로만 기술될 수 있다는 놀라운 사실을 발견한 것입니다. 이것은 복잡도와 논리 사이의 깊은 연결을 보여줍니다.
  • 정리 1: 이 정리는 구조의 집합 T가 NP에 속하면, 해당 구조를 두 번째 순서의 존재론적 논리로 기술할 수 있다는 것을 나타냅니다.

이 텍스트는 복잡도 이론과 논리 사이의 관계에 대한 중요한 인사이트를 제공합니다. Fagin의 정리는 NP 문제를 논리적으로만 기술할 수 있다는 점에서 특히 중요합니다.

 

 

먼저, 주요 용어들부터 이해를 돕기 위해 정리해보겠습니다.

  • NP: 복잡도 이론에서, NP는 주어진 해가 올바른지 다항 시간 내에 확인할 수 있는 문제의 집합을 나타냅니다.
  • Second order: 두 번째 순서의 논리는 변수들이 객체 뿐만 아니라 객체의 집합에 대해서도 양자화될 수 있는 논리 체계입니다.
  • Existential sentence (SOE): 두 번째 순서의 존재론적 문장은 특정 속성을 가진 객체의 집합이 존재한다는 것을 나타내는 문장입니다.

이제 주어진 설명을 토대로 본문의 내용을 해석하겠습니다:

"Characterization of NP without Turing machines": NP를 튜링 머신을 사용하지 않고 특성화하거나 설명하려고 합니다. 일반적으로 NP 문제는 비결정적 튜링 머신으로 다루어지지만, 여기서는 다른 방법을 사용하여 NP를 설명합니다.

"Second order Existential sentence (SOE)": NP를 설명하기 위한 주요 도구로서, 두 번째 순서의 존재론적 문장을 사용합니다.

"NP is the set of structures T such that...": NP는 특정 조건을 만족하는 구조들의 집합인 T로 정의됩니다. 그 조건은 다음과 같습니다:

"there exists a SOE s such that T is a set of structures A such that s is true in A": 특정 두 번째 순서의 존재론적 문장 's'가 있으며, 이 's'는 구조 A 내에서 참이다. 여기서 T는 그러한 모든 구조 A의 집합입니다.

결론적으로, 이 텍스트는 NP 문제를 논리적으로 특성화하는 방법을 설명합니다. 특히, NP 문제는 두 번째 순서의 존재론적 문장에 의해 기술될 수 있으며, 이 문장은 해당 문제의 해결에 대한 정보를 제공합니다.