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

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

7_JUN_7 2023. 10. 30. 14:41

TQBF 문제 – 완전히 양자화된 부울 수식 f가 주어졌을 때, 어떻게 f가 TQBF의 멤버인지 (즉, f가 참인지) 판별할 수 있을까?



주어진 QBF에 대하여 TQBF (즉, 참)인지 여부를 결정하기 위한 간단한 재귀 알고리즘이 있습니다.

\[ Q_1x_1Q_2x_2...Q_nx_n\phi(x_1, x_2,..., x_n) \]

수식에 양자자가 없으면 수식을 그대로 반환할 수 있습니다. 그렇지 않으면 첫 번째 양자자를 제거하고 첫 번째 변수에 대한 두 가능한 값을 모두 확인합니다:

\[ A = Q_2x_2...Q_nx_n\phi(0, x_2,..., x_n) \]
\[ B = Q_2x_2...Q_nx_n\phi(1, x_2,..., x_n) \]

\[ Q_1 \]이 \[ \exists \] (있다면)이면 \[ A \lor B \]를 반환하고, \[ Q_1 \]이 \[ \forall \] (모든)이면 \[ A \land B \]를 반환합니다.


공간 사용 – 입력 크기에 대한 다항식(PSPACE) – 각 재귀 호출은 동일한 공간을 재사용(reuse)할 수 있습니다

 

  • TQBF (True Quantified Boolean Formula) 문제: 완전히 양자화된 (모든 변수에 대해 양자화된) 부울 수식의 참/거짓을 판별하는 문제입니다. 예를 들어, "모든 x에 대하여 어떤 y가 존재하여 x OR y가 참"과 같은 문장의 참/거짓을 판별하는 것을 의미합니다.

 

 

이 텍스트는 QBF (양자화된 부울 함수)의 진릿값을 결정하기 위한 재귀적 알고리즘에 대한 설명입니다.

1. QBF : 양자자 (예: 모든 또는 어떤)와 함께 사용되는 부울 함수입니다.
2. 알고리즘은 수식에서 첫 번째 변수에 대한 양자자를 확인합니다.
3. 양자자가 "있다면"인 경우, 해당 변수에 대해 참(1) 또는 거짓(0) 값 중 하나를 가질 때 수식이 참이 되는지 확인합니다.
4. 양자자가 "모든"인 경우, 해당 변수에 대해 참과 거짓 모두의 값을 가질 때 수식이 참이 되는지 확인합니다.
5. 이 과정을 재귀적으로 반복하여 QBF가 TQBF (즉, 참인 QBF)인지 여부를 결정합니다.

 

공간 사용 – 입력 크기에 대한 다항식(PSPACE) – 각 재귀 호출은 동일한 공간을 재사용할 수 있습니다.

 

  • PSPACE: 입력 크기에 비례하는 다항식 공간만큼의 메모리를 사용하는 문제의 집합을 나타냅니다. TQBF 문제를 풀기 위해 재귀적으로 문제를 해결할 때, 각 재귀 호출마다 새로운 메모리를 필요로 하지 않고 동일한 메모리 공간을 재사용할 수 있습니다. 이러한 특징 때문에 TQBF는 PSPACE 내의 문제로 분류됩니다.

예제 문제



 

공간 요구사항 - 루트부터 잎까지의 경로만 저장(및 재사용)되어야 합니다: 깊이 우선 탐색(DFS)





이 이미지는 양자화된 부울 함수(QBF)에 대한 해석을 나타내는 트리 다이어그램입니다. 주어진 QBF는 `∃x₁∀x₂∃x₃ φ(x₁, x₂, x₃)`로 표시되며, 이는 3개의 변수와 각 변수에 대한 양자자(모두/어떤)를 포함합니다.

1. 트리의 최상단에는 전체 QBF가 표시되어 있습니다.
2. 첫 번째 단계에서는 x₁에 대한 두 가지 가능한 값을 고려합니다: T(참) 또는 F(거짓).
3. 다음 단계에서는 x₂의 값을 고려합니다. `∀` 양자자 때문에 x₂의 모든 가능한 값(T와 F)에 대해 평가해야 합니다.
4. 마지막 단계에서는 x₃에 대한 값을 고려합니다.
5. 트리의 바닥에 도달하면 양자자가 없는 함수 φ의 최종 평가를 나타냅니다. 이 평가는 각 변수 조합에 대한 φ의 결과를 보여줍니다.

트리의 각 분기점에서 "또는(OR)" 또는 "그리고(AND)"와 같은 연산자를 사용하여 다양한 변수 값 조합을 평가합니다.

 

 

이 문장은 트리나 그래프의 깊이 우선 탐색(depth-first traversal)에 관한 것입니다. 깊이 우선 탐색에서는 현재 노드의 자식들을 탐색하기 전에 해당 노드를 완전히 탐색합니다.

"루트부터 잎까지의 경로만 저장(및 재사용)되어야 합니다"는 깊이 우선 탐색의 공간 효율성을 나타냅니다. 즉, 트리나 그래프의 모든 노드를 저장할 필요가 없으며, 현재 탐색 중인 경로만 저장하면 됩니다. 이것은 특히 메모리 사용을 최소화할 때 유용합니다.

 

therefore, a member of TQBF

  1. 첫 번째 그림에서는 다음의 QBF를 보여줍니다: ∃x₁ ∀x₂ ∃x₃ φ(x₁, x₂, x₃)이 QBF를 해결하기 위한 접근 방식을 트리 형태로 나타내었습니다. 각 노드는 변수에 대한 값(T 또는 F)을 나타내며, 트리의 각 레벨은 QBF의 다음 정량자를 나타냅니다. "∃"는 "존재한다"를, "∀"는 "모든"을 의미합니다.
  2. 여기서 φ는 어떤 부울 함수입니다.
  3. 두 번째 그림은 첫 번째 그림의 특정 부분을 확대하여 보여줍니다. φ 함수는 다음과 같이 정의됩니다:그림의 나머지 부분은 x₁, x₂, x₃ 각각에 대한 가능한 값들을 나타내며, 그 값들에 따라 φ 함수의 결과가 어떻게 되는지를 시각화하고 있습니다.
  4. φ(x₁, x₂, x₃) = (x₁ ∨ (x₂ ∨ x₃)) ∧ (~x₁ ∨ x₂ ∨ ~x₃)

요약하면, 이 그림들은 QBF의 해결 방법을 시각적으로 나타내고 있으며, 각 변수에 대한 가능한 값을 통해 주어진 부울 함수 φ의 결과를 파악하는 방법을 설명하고 있습니다.

 

정리: SAT가 P에 속한다면, NP의 모든 문제는 효율적으로 해결될 수 있다.

 

그러나 "증명서(certificate)"를 "찾는" 것에 대해서는 어떻게 할까? 다시 말해서, SAT가 결정 문제(decision problem)이기 때문에, SAT가 P에 속하는 사실은 SAT의 임의의 구성원에 대한 증명서 c를 얻는 것처럼 보이지 않는다. 이것은 SAT가 P의 구성원이라면 가능하게 되는데 - 어떻게 가능한가?

 

만약 SAT가 P에 속한다면, SAT의 임의의 인스턴스(instance)에 대한 증명서를 효율적으로 찾을 수 있음을 보여라.

  1. SAT와 P/NP 문제: SAT는 NP-complete 문제로 알려져 있으며, P=NP 문제의 중심에 있습니다. P=NP라는 것은 클래스 P의 모든 문제가 클래스 NP에도 속하며, NP의 모든 문제가 P에도 속한다는 것을 의미합니다.
  2. 결정 문제와 증명서: 결정 문제는 '예' 또는 '아니오'의 형태로 답을 제공합니다. SAT 문제의 경우, 주어진 논리식이 충족 가능한지 불가능한지를 판단하는 것입니다. 하지만, 충족 가능한 경우, 어떻게 그것이 충족 가능한지에 대한 '증명서' 또는 '증언'이 필요합니다. 이 증명서는 어떤 변수 할당이 논리식을 참으로 만드는지를 보여주는 것입니다.
  3. SAT가 P에 속하는 경우의 증명서: 만약 SAT가 P에 속한다면, 이는 SAT를 효율적으로 해결할 수 있는 알고리즘이 존재한다는 것을 의미합니다. 그러므로, 이 알고리즘을 사용하여 충족 가능한 논리식에 대한 변수 할당(증명서)을 효율적으로 찾을 수 있습니다.

결론적으로, SAT가 P에 속한다면, 그것을 충족시키는 변수 할당(증명서)을 효율적으로 찾을 수 있는 알고리즘이 존재한다는 것을 의미합니다.

< 만약 SAT가 P에 속한다면, SAT의 임의의 인스턴스(instance)에 대한 증명서를 효율적으로 찾을 수 있음을 보여라.>

 

 

f는 OR 연산으로 결합된 2개의 부분 수식으로 "변환될 수 있다."

  • f가 YES 인스턴스라면, 이 두 수식 중 하나(또는 둘 다 가능)는 만족 가능해야 한다.

 


f는 OR 연산으로 결합된 2개의 부분 수식으로 "변환될 수 있다."

- f가 YES 인스턴스라면, 이 두 수식 중 하나(또는 둘 다 가능)는 만족 가능해야 한다.

 



그림에는 세 개의 부분이 있습니다:

1. 첫 번째 부분:
    - f라는 불리언 함수가 주어지며, 다음 세 개의 절로 구성된다:
        1) \(x_1\) OR \(x_2\) OR \(x_3\)
        2) NOT \(x_2\) OR \(x_3\)
        3) \(x_1\) OR \(x_3\) OR NOT \(x_4\)

2. 두 번째 부분:
    - f는 두 개의 부분 수식, \(f_{T_{x1}}\) 및 \(f_{F_{x1}}\)으로 분해된다.
    - \(f_{T_{x1}}\)는 \(x_1\)이 참인 경우의 f를 나타내며, 다음 세 개의 절로 구성된다:
        1) T (참) OR \(x_2\) OR NOT \(x_3\)
        2) NOT \(x_2\) OR \(x_3\)
        3) T (참) OR \(x_3\) OR NOT \(x_4\)

3. 세 번째 부분:
    - \(f_{F_{x1}}\)는 \(x_1\)이 거짓인 경우의 f를 나타내며, 다음 세 개의 절로 구성된다:
        1) F (거짓) OR \(x_2\) OR NOT \(x_3\)
        2) NOT \(x_2\) OR \(x_3\)
        3) F (거짓) OR \(x_3\) OR NOT \(x_4\)

결론적으로, 원래의 함수 f는 \(x_1\)의 두 가능한 값(참 또는 거짓)에 따라 두 개의 부분 수식으로 분해되며, 이 두 부분 수식 중 적어도 하나는 만족 가능해야 합니다.

 

SAT가 P에 속하므로, 다항 시간 안에 SAT를 결정하는 결정적 튜링 기계(dTM)가 있습니다. 이 결정적 튜링 기계를 M이라고 합시다.

  1. M을 사용하여 f가 SAT에 속하는지 여부를 결정합니다.
  2. f가 SAT에 속하면, OR로 결합된 2개의 부분 수식으로 구성된 수식으로 변환합니다.
  3. 이 2개의 부분 수식 중 하나에 M을 사용합니다 - SAT에 속하는 부분 수식을 f1이라고 합시다.
  • SAT는 NP 내의 결정 문제로, 주어진 불리언 함수가 만족 가능한지 아닌지를 결정하는 문제입니다. 여기서 말하는 'P에 속한다'는 SAT 문제를 다항 시간 안에 풀 수 있다는 의미입니다.
  • M은 그러한 다항 시간 결정적 튜링 기계를 나타내며, 주어진 불리언 함수 f가 SAT에 속하는지, 즉 만족 가능한지 여부를 판단할 수 있습니다.
  • f가 SAT에 속하면, 그것을 OR로 연결된 두 개의 부분 수식으로 변환하는 과정을 거칩니다.
  • 마지막으로, 이 두 부분 수식 중 하나가 SAT에 속하는지 확인하기 위해 다시 M을 사용합니다. 이러한 부분 수식 중 SAT에 속하는 것을 f1이라고 합니다.

오라클, 오라클 튜링 기계, 오라클 알고리즘

 

언어 A를 위한 오라클은 문자열 w가 A의 멤버인지 여부를 보고할 수 있는 장치입니다. 오라클 튜링 기계 M^A는 오라클에 질의할 수 있는 추가 기능을 가진 수정된 튜링 기계입니다. M^A가 특별한 오라클 테이프에 문자열을 작성할 때마다 해당 문자열이 A의 멤버인지 아닌지를 단 한 번의 계산 단계에서 알려줍니다. P^A는 오라클 A를 사용하는 다항 시간 오라클 튜링 기계로 결정 가능한 언어의 클래스입니다. NP^A도 마찬가지로 정의됩니다.

 

 

 

"오라클 A"와 "언어 A를 위한 오라클"은 (불행하게도) 교차하여(interchangeably) 사용됩니다.

  • 오라클(Oracle): 복잡도 이론에서 오라클은 어떤 특정한 문제를 즉시 해결할 수 있는 가상의 장치나 엔터티를 의미합니다. 이것은 계산의 어떤 부분에서 "마법처럼" 즉시 답을 제공하는 것으로 생각될 수 있습니다.
  • 오라클 튜링 기계(Oracle Turing Machine): 오라클을 접근할 수 있는 특별한 튜링 기계입니다. 이 기계는 일반적인 튜링 기계의 작동 방식과 같지만, 특정 문제의 해답을 즉시 얻을 수 있는 오라클에 접근하는 기능이 추가되어 있습니다.
  • 오라클 알고리즘(Oracle Algorithm): 오라클을 사용하여 문제를 해결하는 알고리즘입니다. 오라클 알고리즘은 특정 문제의 부분을 오라클에 의존하여 해결합니다.
  • 글에서 언급된 "오라클 A"와 "언어 A를 위한 오라클" 사이의 혼동은, 특정 문제나 언어를 즉시 해결하거나 인식할 수 있는 오라클을 언급할 때 발생하는 용어의 중복을 나타냅니다.

 

  • 언어 A를 위한 오라클: 주어진 언어 A에 속하는 문자열을 즉시 판별할 수 있는 가상의 장치입니다. 즉, 입력 문자열이 언어 A의 일부인지 아닌지를 판별합니다.
  • 오라클 튜링 기계: 표준 튜링 기계와 비슷하나, 언어 A에 대한 오라클에 질의하여 해당 문자열이 언어 A의 일부인지를 즉시 알 수 있는 기능이 추가되었습니다.
  • 오라클 테이프: 오라클 튜링 기계 내에 있는 특별한 테이프로, 이 테이프에 문자열을 작성하면 오라클은 그 문자열이 언어 A에 속하는지 즉시 알려줍니다.
  • P^A: 오라클 A를 활용하여 다항 시간 안에 결정 가능한 언어들의 집합입니다.
  • NP^A: 오라클 A를 활용한 NP 문제에 관련된 언어들의 집합입니다. 이는 P^A와 유사한 방식으로 정의되지만, 비결정적 다항 시간 내에 해결될 수 있는 문제들을 포함합니다.

만약 우리가 SAT를 상수 시간 안에 결정하는 오라클 (즉, 마법 같은 장치)을 가지고 있었다면 어떨까요?

 

예를 들면, p^SAT는 우리가 오라클에게 접근할 수 있을 때 다항 시간 내에 해결할 수 있는 문제의 클래스입니다. 이 오라클은 주어진 SAT 공식이 만족스러운지 여부를 즉시 알려줍니다. SAT는 NP-완전하기 때문에,

 

이는 NP 내의 모든 질문에 답할 수 있는 오라클을 가지고 있는 것만큼 좋습니다. p^SAT = p^NP.

SAT를 만족하지 않는 공식의 언어로 SAT를 나타냅시다. 그러면 SAT는 p^SAT에 속합니다. 실제로, SAT에 오라클 접근 권한이 주어진 경우, 공식 ϕ이 SAT에 있는지 여부를 결정하기 위해 다항 시간 오라클 TM은 오라클에게 ϕ ∈ SAT인지 물을 수 있고, 그런 다음 반대 답변을 출력으로 제공합니다.

"만약 우리가 SAT를 상수 시간 안에 결정하는 오라클 (즉, 마법 같은 장치)을 가지고 있었다면 어떨까요?"

이 문장에서는 오라클이라는 특별한 장치나 시스템을 상상하고 있습니다. 오라클은 어떤 문제를 즉시 해결할 수 있는 기능을 가진 가상의 도구나 기계를 말합니다. 이 문장에서의 오라클은 "SAT"라는 문제를 상수 시간, 즉 고정된 시간 안에 결정하거나 해결할 수 있다고 가정하고 있습니다.

여기서 "SAT"는 결정 문제 중 하나로, 주어진 논리식이 만족 가능한지(즉, 참이 되게 하는 변수의 값을 찾을 수 있는지) 여부를 결정하는 문제를 의미합니다. SAT는 NP-완전 문제로 알려져 있어, 현재로서는 다항 시간 내에 해결할 수 있는 효율적인 알고리즘이 알려져 있지 않습니다.

따라서, 만약 오라클이 SAT 문제를 상수 시간 내에 결정할 수 있다면, 그것은 현재 컴퓨터 과학의 이론과는 크게 다른 놀라운 능력을 가진 것으로 간주됩니다. 이러한 상황을 상상하는 것은 현재 알려진 계산의 한계와는 어떤 방식으로 다를 수 있는지, 그리고 그런 능력이 실제로 가능한지 여부에 대한 질문을 던지게 합니다.

 

 

 

  1. p^SAT는 SAT 문제 (불리안 만족 가능성 문제)에 대한 오라클에 접근할 때 다항 시간 내에 해결할 수 있는 문제의 집합을 나타냅니다. 다시 말해, SAT 문제를 즉시 해결할 수 있는 오라클이 있다면, 어떤 종류의 문제들을 효과적으로 해결할 수 있는지를 나타내는 클래스입니다.
  2. SAT는 NP-완전한 문제입니다. 이는 NP 내의 모든 문제가 SAT로 변환될 수 있다는 것을 의미합니다. 따라서 SAT를 즉시 결정하는 오라클을 가지면 NP 내의 모든 문제에 대한 답을 얻을 수 있게 됩니다.
  3. 글의 마지막 부분은 SAT와 반대되는 문제, 즉 SAT 문제의 부정 버전에 대한 오라클에 접근할 때 어떻게 다른 결과를 얻을 수 있는지 설명합니다. 이는 주어진 공식이 SAT에 속하지 않는 경우, 그 반대 결과를 쉽게 얻을 수 있음을 보여줍니다.

간단히 말해, 만약 우리가 SAT 문제를 상수 시간 안에 결정하는 오라클을 가질 수 있다면, NP 내의 많은 다른 복잡한 문제들도 쉽게 해결할 수 있을 것입니다.

 

티스토리툴바