본문 바로가기
카테고리 없음

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

7_JUN_7 2023. 10. 31. 03:03

새로운 유형의 문제(결정 문제, 계산 문제, 검색 문제, 최적화 문제 등 참조)

 

약속 문제 [ESY84] (P, Q)는 다음과 같은 형태를 가지고 있습니다:

  • 인스턴스 x.
  • 약속 P(x).
  • 질문 Q(x)?

우리는 P와 Q가 결정 가능한 술어라고 가정합니다. 모든 입력에서 정지하는 결정론적 튜링 기계 M이 (P, Q)를 푸는 경우:

 

∀x[P(x) → [Q(x) ↔ M(x) = “예”]]

 

만약 P(x)가 거짓이면 M이 x 입력에서 어떻게 동작하는지는 신경 쓰지 않습니다. 만약 M이 (P, Q)를 푼다면, 우리는 L(M)을 (P, Q)의 해결책이라고 부릅니다. 일반적으로 약속 문제는 많은 해결책을 가질 수 있으며, 우리는 주로 복잡도가 낮은 해결책이 있는지를 파악하는 데 관심이 있습니다. 만약 해결책 L이 있고 그것이 P에 속한다면, 우리는 (P, Q)가 P에 속한다고 말합니다.

약속 문제는 결정 문제나 최적화 문제와 같은 전통적인 계산 문제의 일종입니다. 주요 차이점은 약속 문제가 '약속' 된 입력 집합에만 대해서만 답을 주어야 한다는 것입니다. 이것은 특정한 조건 P(x)를 만족하는 입력 x에만 대한 문제의 답을 고려한다는 것을 의미합니다.

결정론적 튜링 기계 M은 문제 (P, Q)를 해결하려면 모든 약속된 입력에 대해 올바르게 동작해야 합니다. 그러나 약속되지 않은 입력에 대해서는 그 동작이 어떤지 신경 쓰지 않습니다.

이러한 유형의 문제는 특정 조건을 만족하는 입력에만 대한 해결책을 찾는 연구에서 유용하게 사용될 수 있습니다.

예제 문제)

  • 입력: 명제 논리의 공식 x
  • 약속: 만족하는 대입의 수는 1 이하입니다.
  • 속성: x는 만족할 수 있습니다.

(Unique-SAT):

  • 인스턴스: 명제 논리의 공식 F
  • 약속: F는 0 또는 1의 만족하는 대입을 가집니다.
  • 질문: F는 만족하는 대입을 가지고 있나요?
  •  

 

  1. 첫 번째 이미지에서는 명제 논리의 어떤 공식 x에 대한 설명을 제공합니다. 이 공식 x는 최대 하나의 만족하는 대입을 가질 수 있으며, 이 공식이 만족될 수 있는지 (즉, 참으로 만들 수 있는 대입이 있는지) 여부도 표시됩니다.
  2. 두 번째 이미지는 Unique-SAT라는 문제에 대한 설명입니다. Unique-SAT는 명제 논리의 공식 F에 대해 주어지며, 이 공식은 만족하는 대입이 없거나 정확히 하나만 있을 수 있습니다. 주요 질문은 공식 F가 만족하는 대입을 가지고 있는지 여부입니다.

명제 논리에서 "만족하는 대입"이라는 용어는 주어진 논리 공식을 참으로 만드는 변수의 대입을 의미합니다. 예를 들어, 공식 �∨�는 �=참 및 �=거짓일 때 참이 됩니다. 따라서 이 대입은 공식을 만족한다고 할 수 있습니다.

Unique-SAT 문제는 특정한 약속 조건 하에서 SAT 문제의 변형입니다. 여기서의 약속은 주어진 논리 공식이 정확히 하나의 만족하는 대입을 가지거나 전혀 없을 수 있다는 것입니다.

 

인스턴스 (instance) 약속 (promise) 질문 (question

 

많은 자연 문제들은 실제로 약속 문제들입니다. 예를 들어, 다음 문제를 고려해보세요: 주어진 방향성 비순환 그래프에서, 그래프가 길이 10의 경로를 가지고 있는지 확인합니다. '예' 인스턴스들은 길이 10의 경로를 가진 방향성 비순환 그래프이며, '아니오' 인스턴스들은 길이 10의 경로가 없는 방향성 비순환 그래프입니다. 약속은 방향성 비순환 그래프의 집합입니다. 이 예시에서, 주어진 그래프가 순환이 있는지 확인하는 것은 매우 쉽습니다. 그러나, 약속된 속성을 평가하는 것은 어려울 수 있습니다. 예를 들어, "해밀턴 그래프가 주어졌을 때, 그래프에 크기 4의 순환 구조가 있는지 확인하세요."라는 문제를 고려해보세요. 이제 약속은 NP-난해로 평가하기 어렵지만, 크기 4의 순환을 확인하는 약속 문제는 다항 시간 안에 해결될 수 있습니다.

  1. 인스턴스 (instance): 문제의 입력 예시나 상황을 의미합니다. 예를 들어, 방향성 비순환 그래프나 해밀턴 그래프가 인스턴스가 될 수 있습니다.
  2. 약속 (promise): 문제에서 주어진 특정 조건이나 속성을 의미합니다. 예로, 길이 10의 경로를 가진 그래프나 크기 4의 순환 구조를 가지는 그래프와 같은 조건들이 있습니다.
  3. 질문 (question): 문제에서 요구하는 특정 답이나 해결을 찾는 것을 의미합니다. 예로, 그래프가 길이 10의 경로나 크기 4의 순환 구조를 가지고 있는지 확인하는 것과 같은 질문들이 있습니다.

이 텍스트는 "약속 문제"에 대한 설명을 제공합니다. 약속 문제는 일반적인 계산 문제와는 다르게, 약속된 특정 조건 하에서만 문제를 해결하도록 요구됩니다. 이러한 문제의 핵심은 약속된 조건 하에서 문제를 평가하거나 해결하는 것이 일반적인 상황보다 쉬울 수도, 어려울 수도 있다는 것입니다.

 

결정 문제 – 약속 문제의 특별한 경우
(인스턴스, 약속, 질문)

 

결정 문제는 모든 문제 인스턴스에 대해 약속이 일반적으로 적용되는 약속 문제의 특별한 경우입니다. 예를 들어, SAT는 인스턴스가 부울식 F인 약속 문제로 간주될 수 있습니다. 약속 P(x)는 모든 수식 F에 대해 적용되며, 질문은 "F는 만족할 수 있는가?" 입니다.

  1. 결정 문제 (Decision problem): '예' 또는 '아니오'로 답할 수 있는 계산 문제를 의미합니다.
  2. 약속 문제 (Promise problem): 일반적인 계산 문제와는 다르게, 약속된 특정 조건 하에서만 문제를 해결하도록 요구됩니다.
  3. 인스턴스 (Instance): 문제의 입력 예시나 상황을 의미합니다. 예로, 부울식 F가 인스턴스가 될 수 있습니다.
  4. 약속 (Promise): 문제에서 주어진 특정 조건이나 속성을 의미합니다. 예로, 모든 수식 F에 대해 적용되는 P(x)와 같은 조건들이 있습니다.
  5. 질문 (Question): 문제에서 요구하는 특정 답이나 해결을 찾는 것을 의미합니다. 예로, 수식 F가 만족할 수 있는지 확인하는 것과 같은 질문들이 있습니다.

이 텍스트는 결정 문제가 약속 문제의 특별한 경우임을 설명합니다. 결정 문제는 모든 문제 인스턴스에 대한 약속이 일반적으로 적용되므로, 약속 문제의 한 형태라 할 수 있습니다. SAT 문제는 약속 문제의 예로 들어집니다. SAT 문제는 주어진 부울식 F가 만족할 수 있는지 (즉, 참인 값을 가질 수 있는지)를 판별하는 문제입니다.

BPP(제한된 오류 확률 다항식 시간)

 

대안적으로, BPP는 결정론적 튜링 기계만을 사용하여 정의될 수 있습니다. 언어 L이 BPP 내에 있다면, 다항식 p와 결정론적 튜링 기계 M이 존재하여 다음 조건들이 만족됩니다:

  1. 모든 입력에 대해 M은 다항 시간 안에 실행됩니다.
  2. L 내의 모든 x에 대해, 길이가 p(|x|)인 문자열 y의 비율에서 M(x, y) = 1을 만족하는 것이 2/3 이상입니다.
  3. L 내의 모든 x가 아닌 경우, 길이가 p(|x|)인 문자열 y의 비율에서 M(x, y) = 1을 만족하는 것이 1/3 이하입니다.
  • BPP (Bounded error probabilistic polynomial time): BPP는 확률적 튜링 기계가 다항 시간 내에 올바른 답을 주는 확률이 항상 특정 경계 이상이 되도록 하는 복잡도 클래스를 의미합니다.
  • 결정론적 튜링 기계: 항상 동일한 출력을 내놓는 계산 모델입니다. 반면, 확률적 튜링 기계는 동일한 입력에 대해 다른 출력을 낼 수 있습니다.
  • 여기서 주어진 정의는 BPP를 결정론적 튜링 기계를 사용하여 표현하는 대안적인 방법입니다. 기본적으로, 언어 L의 문자열 x에 대해서 2/3 이상의 확률로 올바른 답을 제공하는 결정론적 튜링 기계가 있어야 하며, x가 L에 속하지 않는 경우에는 1/3 이하의 확률로만 올바른 답을 제공해야 합니다.

이러한 정의는 BPP의 복잡도 클래스를 이해하는 데 도움이 되는 다른 관점을 제공합니다.

 

확률적 튜링 머신PTM(cf nTM)

우리는 이제 확률적 튜링 기계 (PTMs)를 정의합니다. 구문론적으로, PTM은 비결정론적 튜링 기계와 다르지 않습니다. 그것은 두 개의 전이 함수 δ₀, δ₁을 갖는 튜링 기계입니다. 차이점은 가능한 모든 계산의 그래프를 어떻게 해석하는지에 있습니다: 튜링 기계가 받아들이는 시퀀스가 존재하는지 여부를 묻는 대신, 이것이 일어나는 선택의 비율이 얼마나 큰지 묻습니다. 더 정확하게 말하면, M이 PTM이라면, 계산의 모든 단계에서 M은 적용할 전이 함수 중 하나를 무작위로 선택합니다 (δ₀을 적용할 확률이 절반, δ₁을 적용할 확률이 절반입니다). 우리는 M이 적어도 2/3의 확률로 올바른 답을 출력하면 언어를 결정한다고 말합니다.

 

 

각 단계에서 가능한 2가지 전환 기능 중 하나가 무작위로 "선택"됩니다.

  • 확률적 튜링 기계 (Probabilistic Turing Machines, PTMs): PTM은 전통적인 튜링 기계와는 달리 무작위성을 포함하며, 계산의 각 단계에서 두 개의 전이 함수 중 하나를 무작위로 선택하여 적용하는 기계입니다.
  • 전이 함수 (Transition Functions): 튜링 기계의 현재 상태와 테이프 상의 현재 기호를 기반으로 다음 상태, 기호 및 머리의 방향을 결정하는 함수입니다.
  • 여기서 주요한 차이점은 비결정론적 튜링 기계가 어떤 입력에 대해 여러 가능한 계산 경로를 가질 수 있으나, 확률적 튜링 기계는 그 경로 중 하나를 무작위로 선택합니다. 그리고 그 선택은 확률에 따라 이루어집니다.

이러한 확률성 때문에, 확률적 튜링 기계는 특정 입력에 대한 출력을 "올바르게" 계산하는 확률이 특정 경계 이상이어야 한다는 조건을 만족해야 합니다.

BPP using PTM

T: N → N과 L⊆ {0, 1}*에 대해, 만약 모든 x ∈ {0, 1}*에 대해 PTM M이 T(|x|) 스텝 내에 무작위 선택에도 불구하고 중단하고, Pr[M(x) = L(x)] ≥ 2/3이면, M은 T(n) 시간 안에 L을 결정한다고 합니다. 여기서 L(x) = 1은 x가 L에 속하면, 그리고 L(x) = 0은 x가 L에 속하지 않으면 표시됩니다. 우리는 O(T(n)) 내에 PTMs에 의해 결정된 언어의 클래스를 BPTIME(T(n))으로 표기하고, BPP를 ∪_c BPTIME(n^c)로 정의합니다.

 

 

P는 BPP의 부분집합입니다 - 왜일까?

 

열린 문제 : P = BPP?

  1. 확률적 튜링 기계 (PTM)와 시간 복잡도: PTM은 어떤 언어 L을 T(n) 시간 안에 "결정"할 수 있다고 합니다. 이는 입력 x에 대해 PTM M이 T(|x|)의 스텝 내에서 중단하고, 그 결과가 L(x)와 일치할 확률이 2/3 이상이어야 한다는 것을 의미합니다.
  2. BPTIME(T(n)): 이는 O(T(n)) 복잡도로 동작하는 PTM에 의해 결정될 수 있는 언어의 클래스를 나타냅니다.
  3. BPP: 확률적 다항 시간 내에 결정될 수 있는 언어의 클래스입니다. BPP는 모든 상수 c에 대해 BPTIME(n^c)의 합집합으로 정의됩니다.
  4. P와 BPP의 관계: P는 결정론적 다항 시간에 속하는 문제들의 클래스를 나타내며, BPP는 확률적 다항 시간에 속하는 문제들의 클래스를 나타냅니다. P는 항상 BPP 내에 있습니다. 즉, 결정론적 다항 시간 내에 해결될 수 있는 모든 문제는 확률적 다항 시간 내에도 해결될 수 있습니다.
  5. 열린 문제: 현재까지 P와 BPP가 정확히 같은 클래스인지 아닌지는 알려진 바 없습니다. 이는 컴퓨터 과학에서 아직 해결되지 않은 중요한 문제 중 하나입니다.

이 내용은 복잡도 이론에서 중요한 개념들을 다루고 있습니다. P와 BPP, 그리고 PTM은 어떤 문제들이 어느 정도의 자원(시간, 공간)을 사용하여 효과적으로 해결될 수 있는지에 대한 연구의 핵심 주제입니다.

불린 쿼리 정의: 세트 B에 대한 불린 쿼리는 불린 연결어 ∧, ∨, ¬를 사용하여 구성된 명제 공식입니다. 여기서 원자 공식은 모두 m ∈ B 형태입니다. 여기서 m은 양의 정수입니다. 예를 들면, 공식 (5 ∈ B) ∧ ¬(67 ∈ B) ∨ ¬(42 ∈ B) ∧ (87 ∈ B) 입니다.

 

진리표 축소성 정의: 세트 A가 세트 B에 진리표 축소 가능하다고 정의하면, 모든 n에 대해 f(n)이 B에 대한 불린 쿼리이며, n이 A에 있으면 그리고 그럴 때에만 B가 f(n)을 만족하는 계산 가능한 함수 f가 있을 때입니다. 또한, f(n)의 불린 쿼리 내의 원자 공식 수에 대한 상한 값이 있다면, 우리는 A가 B에 경계된 진리표 축소 가능하다고 말합니다.

 

A의 진리표 축소성: A가 B에 진리표 축소 가능하다면: (1) 계산 가능한 함수 f가 있습니다. (2) f(n)은 B에 대한 불린 쿼리로 B에 대한 유한한 수의 멤버십 질문으로 구성됩니다. (3) n이 A에 속하면, 그리고 그럴 때에만 B가 f(n)을 만족합니다.

 

  1. 불린 쿼리: 세트 B에 대한 질문입니다. 이 쿼리는 불린 연산자를 사용하여 B의 특정 원소의 멤버십에 대한 질문을 결합한 명제 공식입니다.
  2. 진리표 축소성: 하나의 집합 A의 문제를 다른 집합 B의 문제로 "축소"하는 방법을 나타내는 개념입니다. 특히, A의 문제를 B의 불린 쿼리로 변환하는 함수 f가 있을 때, A는 B에 진리표 축소 가능하다고 합니다.
  3. 경계된 진리표 축소성: 축소성의 특별한 형태입니다. 이 경우, 불린 쿼리 내의 원자 공식의 수에 고정된 상한 값이 있습니다.

요약하면, 이 개념은 어떻게 하나의 집합이나 문제가 다른 것으로 "축소"될 수 있는지를 설명하는 것입니다. 이는 복잡도 이론에서 중요한 개념 중 하나로, 문제의 복잡도를 비교하거나 한 문제의 어려움을 다른 문제의 어려움을 통해 설명하는 데 사용됩니다.

P = NP일 경우, SAT는 P-선택적 집합에 진리표 축소 가능하다.

 

집합 A가 다음 조건을 만족할 때 P-선택적이라고 합니다: 다항 시간 내에 계산 가능한 함수 f(이를 p-선택자 함수라고 부름)가 존재하여, 어떤 두 문자열 x와 y에 대해서, f(x,y)는 {x,y} 중 하나이며, x나 y 중 하나가 A에 있으면, f(x,y)도 A에 있습니다.

 

P 내의 어떤 언어 L도 P-선택적이다 - 왜 그런가?

  1. P-선택적 집합: P-선택적 집합은 특정 함수를 사용하여 그 집합 내의 두 원소 중 하나를 선택할 수 있는 집합입니다. 이 함수는 다항 시간에 실행될 수 있으며, 선택된 원소도 원래 집합에 포함되어 있습니다.
  2. P = NP와 SAT의 진리표 축소성: P와 NP가 같다면, SAT 문제(불린 충족 가능성 문제)는 P-선택적 집합에 진리표로 축소될 수 있다는 것을 의미합니다. 이는 P = NP일 때 복잡도 클래스 간의 관계에 관한 중요한 사실입니다.
  3. P 내의 언어가 P-선택적인 이유: P 내의 모든 언어는 다항 시간에 결정될 수 있습니다. 따라서, 두 문자열 x와 y를 갖고 그 중 하나를 선택하는 함수도 다항 시간에 작동할 수 있습니다. 만약 x나 y 중 하나가 P 내의 언어에 속한다면, 함수에 의해 선택된 문자열도 그 언어에 속할 것입니다.

요약하면, 여기서 주요 개념은 복잡도 클래스, 특히 P와 NP, 그리고 집합 또는 언어의 특정 성질 간의 관계입니다. P-선택적 집합은 그 집합의 원소를 선택하는 방법에 관한 특별한 성질을 가지고 있으며, 이는 P와 NP와 같은 복잡도 클래스의 문제와 관련이 있습니다.

 

티스토리툴바