[전산학특강] 전산학특강

카테고리 없음

[전산학특강] 전산학특강 - 6(1)

7_JUN_7 2023. 10. 30. 14:23

예제 1 k-클리크 문제

다항 시간 검증기

입력: (G, k, c)
1. G에서 c가 k개의 노드의 집합인지 확인한다.
2. G가 c 내의 노드들을 연결하는 모든 간선을 포함하고 있는지 확인한다.
3. 둘 다 만족하면, '수락'한다. 그렇지 않으면, '거부'한다.

다항 시간 비결정적 알고리즘

입력: (G, k), 여기서 G는 그래프이다.
1. 비결정적으로 G의 k개의 노드의 부분 집합 c를 선택한다.
2. G가 c 내의 노드들을 연결하는 모든 간선을 포함하고 있는지 확인한다.
3. 만약 그렇다면, '수락'한다. 그렇지 않으면, '거부'한다.

k-클리크 문제 (k-clique problem):

그래프 내에서 주어진 k 크기의 완전 그래프(모든 노드가 서로 연결된 부분 그래프)를 찾는 문제입니다. 예를 들어, k가 3이라면 3-클리크(3개의 노드로 구성된 완전 그래프)를 찾는 문제가 됩니다. k-클리크 문제는 NP-완전 문제(NP-complete problem)로 알려져 있어서, 현재까지 알려진 효율적인 다항 시간 알고리즘이 없습니다.

다항 시간 검증기 (polynomial time verifier):

NP 문제의 정의와 관련이 있습니다. 어떤 문제가 NP 내에 있다면, 그 문제의 해(solution)를 주어진 경우, 그것이 정말로 문제의 해인지를 다항 시간 내에 검증할 수 있어야 합니다. 즉, k-클리크 문제의 경우, 특정 부분 그래프가 k-클리크인지 아닌지를 다항 시간 내에 판단할 수 있는 검증기가 있어야 합니다.

다항 시간 비결정적 알고리즘 (polynomial time nondeterministic algorithm):

NP 문제를 해결할 수 있는 비결정적 알고리즘을 의미합니다. 이런 알고리즘은 "마법의 오라클"을 가정하에 가능한 모든 해를 동시에 탐색하며, 다항 시간 내에 문제의 해를 찾아낼 수 있다고 가정합니다. 현재 실제 컴퓨터로는 이러한 비결정적 알고리즘을 실행할 수 없지만, 이론적인 컴퓨터 과학의 영역에서는 중요한 개념입니다

이 알고리즘들은 k-클리크 문제를 다루고 있습니다. k-클리크 문제는 그래프 내에서 주어진 크기의 완전 그래프 (모든 노드가 서로 연결된 부분 그래프)를 찾는 문제입니다.
V는 다항 시간 검증기로, 어떤 부분 집합 c가 k-클리크인지를 판단하는 알고리즘입니다. c가 k개의 노드를 가지고 있으며, c 내의 모든 노드들이 서로 연결되어 있으면 그것은 k-클리크입니다.
N은 비결정적 알고리즘으로, 그래프 G에서 가능한 모든 k개의 노드의 부분 집합을 "마법의 오라클"처럼 동시에 검사하여 k-클리크를 찾습니다. 비결정적 알고리즘이 실제 컴퓨터에서 실행될 수는 없지만, 이론적으로는 NP 문제를 해결하는 데 사용됩니다.

NTIME(t(n)):

NTIME(t(n))은 모든 언어 L의 집합을 나타냅니다. 이 언어 L은 O(t(n)) 시간 안에 비결정적 튜링 기계로 결정될 수 있습니다.

여기서 t(n)은 어떤 함수를 나타냅니다. 이 함수는 주어진 입력의 크기 n에 대한 비결정적 튜링 기계의 실행 시간을 제한합니다.

NP = ⋃ₖ NTIME(n^k):

NP는 비결정적 다항 시간 내에 해결될 수 있는 모든 문제의 집합입니다. 이 표현은 NP가 모든 가능한 다항 시간 복잡도(즉, n, n^2, n^3, ...)를 갖는 언어들의 합집합임을 나타냅니다.
간단히 말해, NP는 주어진 어떤 다항 함수로 시간 복잡도를 제한할 수 있는 모든 비결정적 튜링 기계로 해결될 수 있는 문제들의 집합입니다.

튜링 기계는 계산 가능한 모든 문제를 풀 수 있는 이론적인 기계입니다. 그 중에서도 비결정적 튜링 기계는 여러 가능한 상태로 "동시에" 전이할 수 있는 능력을 갖습니다.
NP 문제들은 현재까지 다항 시간 내에 결정적 방법으로 해결될 수 있는지 아직 알려지지 않았습니다. 하지만, 비결정적 튜링 기계를 사용하면 다항 시간 내에 해결될 수 있습니다.

P와 NP 문제

P: 멤버십(소속)을 빠르게 결정할 수 있는 언어의 집합 NP: 멤버십을 빠르게 검증할 수 있는 언어의 집합

"빠르게" = "다항 시간 솔버빌리티(해결 가능성)"

이 둘은 같은 것일까?

"공간" 복잡도에 대해서는 어떨까? PSPACE = NPSPACE임이 밝혀졌다!

이것은 무엇을 의미하는가? "비결정성"은 계산 중에 사용되는 공간의 양에만 관심이 있다면 효율적으로 시뮬레이션될 수 있다.

비결정성은 자원인가? (cf. 시간, 공간, 네트워크 대역폭, 랜덤 비트 등...)

P vs NP: P와 NP의 정확한 관계는 컴퓨터 과학에서 아직 미해결된 중요한 문제입니다. P는 다항 시간 내에 해결할 수 있는 문제의 집합을 나타내며, NP는 문제의 답을 다항 시간 내에 검증할 수 있는 문제의 집합을 나타냅니다.
PSPACE vs NPSPACE: 공간 복잡도는 알고리즘이 실행되는 동안 필요한 메모리 양을 측정하는 것입니다. PSPACE는 결정적 튜링 기계에서 다항 공간을 사용하여 해결할 수 있는 문제들의 집합이며, NPSPACE는 비결정적 튜링 기계에서 그러한 문제들의 집합입니다. 여기서 중요한 것은 PSPACE와 NPSPACE가 동일하다는 것입니다. 이것은 공간 복잡도 측면에서 비결정성이 결정성을 초월하지 않음을 의미합니다.
비결정성: 비결정적 계산은 여러 가능한 계산 경로 중 하나가 올바른 답을 제공하면 그 답을 수용하는 계산 모델입니다. 비결정성이 다른 계산 자원(예: 시간, 공간)과 어떻게 관련되는지에 대한 질문은 중요한 연구 주제입니다. 일반적으로 비결정성이 시간과 공간, 네트워크 대역폭, 랜덤 비트 등의 다른 자원과 어떻게 상호 작용하는지 연구하는 것은 계산 복잡도 분야의 중심적인 주제 중 하나입니다.

계산 중에 사용되는 "최대 셀의 수"만을 고려하며, 최대 단계 수는 고려하지 않습니다.

이 문장은 계산의 복잡도를 측정할 때 고려하는 두 가지 주요 요소 중 하나에만 중점을 둡니다. 일반적으로 알고리즘의 성능을 측정할 때 "시간 복잡도"와 "공간 복잡도"를 모두 고려합니다.

시간 복잡도: 알고리즘이 얼마나 많은 시간이 필요한지 나타내는 것으로, "최대 단계 수"와 관련됩니다.
공간 복잡도: 알고리즘이 얼마나 많은 메모리를 사용하는지 나타내는 것으로, "최대 셀의 수" 또는 사용된 메모리 양과 관련됩니다.

제공된 이미지는 결정적(deterministic) 방식과 비결정적(nondeterministic) 방식의 계산을 나타냅니다. 결정적 방식은 모든 입력에 대해 명확한 계산 경로를 가지지만, 비결정적 방식은 여러 가능한 계산 경로를 가집니다. 만약 한 경로에서 "수락(accept)" 상태를 찾으면 그 입력은 수락되며, 모든 경로에서 "거절(reject)" 상태만 찾으면 그 입력은 거절됩니다.

이 설명에서 강조된 부분은 공간 복잡도에 관한 것입니다. 계산 중에 필요한 셀(메모리 공간)의 최대 수만 중요하다는 것을 의미합니다.

만족성 문제

문제. 변수들이 TRUE와 FALSE의 값을 가질 수 있다는 것을 기억하십시오. 이러한 변수들을 부울 변수라고 합니다(0.2절 참조). 보통, TRUE는 1로, FALSE는 0으로 표현합니다. AND, OR, NOT 부울 연산은 각각 ∧, ∨, ¬ 기호로 표현되며, 다음 목록에서 설명됩니다. ¬ 기호를 대신하여 오버바를 사용하여 나타냅니다. 따라서 ¬x는 x의 오버바로 나타냅니다.

부울 수식은 부울 변수와 연산을 포함한 표현식입니다. 예를 들면,

다음은 부울 수식입니다. 부울 수식이 만족할 수 있다면 0들과 1들의 변수 할당이 수식을 1로 평가하게 만듭니다. 앞서의 수식은 x = 0, y = 1, z = 0의 할당으로 인해 ϕ를 1로 평가하므로 만족합니다. 우리는 이 할당이 ϕ를 만족한다고 말합니다. 만족 가능성 문제는 부울 수식이 만족 가능한지 테스트하는 것입니다. 따라서,

SAT = {ϕ | ϕ는 만족 가능한 부울 수식입니다}

"예" 인스턴스의 전체 집합 – 문자열로 인코딩됨 [그래서 우리는 언어를 가지고 있다]

이 문서는 부울 논리와 관련된 기본 개념을 설명하고 있습니다. 부울 변수는 TRUE 또는 FALSE의 두 가지 값을 가질 수 있으며, 일반적으로 1(참)과 0(거짓)으로 표현됩니다. 주요 부울 연산자인 AND(∧), OR(∨) 및 NOT(¬)의 동작도 명시되어 있습니다.

부울 수식은 부울 변수와 이러한 연산자를 사용하여 구성된 표현식입니다. 만족성 문제는 주어진 부울 수식에 대해 특정 변수 값 할당이 수식을 TRUE로 만드는지(즉, '만족'하는지) 확인하는 문제입니다.

이 문장은 컴퓨터 과학의 복잡성 이론에서 언어의 개념과 연결되어 있습니다. 복잡성 이론에서 "언어"는 특정 문제의 모든 "예" 인스턴스로 구성된 집합을 의미합니다. 여기서 "예" 인스턴스는 주어진 문제에 대한 양의 해결책을 의미합니다. 예를 들어, 만족성 문제(SAT)의 경우 "예" 인스턴스는 주어진 불리언 수식이 참이 될 수 있는 변수 할당을 가리킵니다.

문장에서 언급된 "문자열로 인코딩됨"은 문제의 인스턴스를 문자열 형태로 표현한다는 것을 의미합니다. 이러한 문자열 인코딩은 복잡성 이론에서 문제 인스턴스를 공식화하고 분석하는 데 사용됩니다.

양자화된 부울 식(Quantified Boolean formulas)

양자화된 부울 식은 변수들에 대한 양자자(quantifiers)를 포함한 부울 식을 말합니다. 이러한 식에서 사용되는 변수의 값 집합은 {0,1}입니다.

예를 들어, φ = ∀x ∃y [(x ∨ y) ∧ (¬x ∨ y)]는 양자화된 부울 식입니다. 여기서 φ는 참(true)입니다. 그러나 양자자 ∀x와 ∃y의 순서가 바뀌면 φ는 거짓(false)이 됩니다.

만약 어떤 부울 식의 모든 변수가 양자자의 범위 내에 있다면, 그 식은 "완전하게 양자화된(fully quantified)"라고 합니다. 완전하게 양자화된 부울 식은 "문장(sentence)"이라고도 하며, 항상 참이거나 거짓 중 하나입니다. 예를 들어, 위의 φ 식은 완전하게 양자화된 식입니다. 그러나 처음의 ∀x 부분을 제거하면, φ는 더 이상 완전하게 양자화되지 않아 참 또는 거짓으로 판단할 수 없습니다.

TQBF 문제는 완전하게 양자화된 부울 식이 참인지 거짓인지를 결정하는 문제입니다. 언어의 정의는 다음과 같습니다:

TQBF = {⟨φ⟩ | φ는 참인 완전하게 양자화된 부울 식이다}

간단히 말하면, 이 글은 양자화된 부울 식의 정의와 그것이 어떻게 "완전하게 양자화된" 부울 식이 되는지에 대해 설명하고 있습니다. TQBF 문제는 이러한 식이 참인지 거짓인지를 판단하는 문제입니다.

만족성 문제는 TQBF 문제의 특별한 경우임을 유의하십시오 – 왜일까?

만족성 문제는 PSPACE의 멤버임 - 직관

주어진 수식 f가 n개의 부울 변수를 가진다고 가정하자.
우리는 다시 사용할 수 있는 n개의 비트가 필요하다.

0을 거짓과 연관시키고 1을 참과 연관시키십시오. 그런 다음 모든 가능한 할당은 0과 1의 n 비트로 표현될 수 있다. 가능한 경우의 수는 2^{n}개이다.

간단히 말해서, 우리는 모든 0 (즉, 모든 변수에 거짓 값을 할당하여 수식을 만족시킬 수 있는지)을 확인한다. 만약 그렇다면, 우리는 끝났다. 그렇지 않으면, 우리는 이전 숫자에 1을 더하여 다음 "숫자"를 확인한다.

f가 만족스러운지 여부를 판단하기 위해 "n 비트"만 필요하다.

간단히 설명하면, 만족성 문제는 주어진 부울 수식이 참으로 평가될 수 있는 변수의 값 할당이 있는지 확인하는 문제입니다. TQBF 문제는 만족성 문제의 확장으로 볼 수 있으며, 양자화된 부울 식의 참과 거짓을 판단합니다. 만족성 문제의 경우, 각 변수에 대해 참과 거짓을 할당하는 모든 가능한 조합을 표현하기 위해 n 비트만 있으면 충분하므로, 이 문제는 PSPACE에 속한다고 할 수 있습니다.

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

그렇지만, "증명서(certificate)"를 "찾는" 것에 대해서는 어떠한가? 다시 말해, SAT가 결정 문제(decision problem)이기 때문에, SAT가 P에 속한다는 사실이 임의의 SAT의 구성원에 대한 증명서 c를 우리에게 가져다 주지 않을 것 같다. 이것이 가능해지는 것은 SAT가 P의 멤버일 경우이다 - 어떻게 가능한가?

SAT는 만족성 문제로, 주어진 부울 논리식이 참인 값을 갖는 변수 할당이 있는지 확인하는 NP-완전 문제입니다.
P는 다항 시간 내에 해결될 수 있는 결정 문제의 집합을 나타냅니다.
NP는 주어진 증명서(certificate)를 사용하여 다항 시간 내에 검증될 수 있는 문제의 집합을 나타냅니다.
만약 SAT가 P에 속하면, 이는 모든 NP 문제도 P에 속할 수 있다는 것을 의미합니다. 그 이유는 SAT가 NP-완전하므로, NP의 모든 문제가 SAT로 환원될 수 있기 때문입니다.
문서에서 언급한 "증명서"는 NP 문제의 솔루션을 검증하는 데 사용되는 정보입니다. SAT가 P에 속하면, 결정 문제의 답만을 알려줄 뿐, 실제로 어떻게 그 답에 도달했는지에 대한 증명서(certificate)를 제공하지는 않습니다.
그러나, SAT가 P에 속하면, 이는 실제로 다항 시간 내에 SAT 문제의 솔루션을 찾을 수 있다는 것을 의미하므로, 이를 사용하여 증명서(certificate) 또한 구할 수 있습니다.

정리: P는 PSPACE의 부분집합이다.

증명:

함수 t: N → R^+ 가 주어졌을 때, 시간 복잡도 클래스 TIME(t(n))은 O(t(n)) 시간 내의 튜링 기계로 결정할 수 있는 모든 언어의 집합을 의미합니다.

P는 다항 시간 내에 결정 가능한 언어의 클래스입니다. 다른 말로 하면, P는 k에 대해 TIME(n^k)의 합집합입니다.

함수 f: N → R^+ 가 주어졌을 때, 공간 복잡도 클래스 SPACE(f(n))와 NSPACE(f(n))은 다음과 같이 정의됩니다:

SPACE(f(n)) = { L | L은 O(f(n)) 공간의 결정적 튜링 기계에 의해 결정되는 언어 }
NSPACE(f(n)) = { L | L은 O(f(n)) 공간의 비결정적 튜링 기계에 의해 결정되는 언어 }

PSPACE는 다항 공간 내에 결정 가능한 언어의 클래스입니다. 다른 말로 하면, PSPACE는 k에 대해 SPACE(n^k)의 합집합입니다.

만약 언어 L이 P의 구성원이라면, 정의에 따라, 어떤 양의 정수 k에 대하여 O(n^{k}) 안에 L을 결정하는 dTM M이 존재한다. M은 O(n^{k})보다 많은 셀을 "볼" 수 없다. 사실, TIME(O(n^{k}))는 SPACE(O(n^{k}))의 부분집합이다. 따라서, L은 반드시 PSPACE의 구성원이어야 한다.

열린 문제: P = PSPACE인가? NP와 PSPACE는 어떤가? NP는 PSPACE의 부분집합인가?

시간 복잡도: 어떤 문제를 해결하기 위한 알고리즘의 수행 시간을 나타내는 척도입니다. 위의 내용에서, O(t(n)) 시간 복잡도를 가지는 튜링 기계로 결정될 수 있는 언어들의 집합을 TIME(t(n))이라고 합니다.
공간 복잡도: 알고리즘의 수행에 필요한 메모리 공간을 나타내는 척도입니다. SPACE(f(n))와 NSPACE(f(n))는 각각 결정적 튜링 기계와 비결정적 튜링 기계로, 주어진 O(f(n)) 공간 내에서 결정될 수 있는 언어들의 집합을 나타냅니다.
P와 PSPACE: 이 두 클래스는 계산 복잡도 이론에서 중요한 역할을 합니다. P는 다항 시간 복잡도로 결정될 수 있는 문제들의 집합이며, PSPACE는 다항 공간 복잡도로 결정될 수 있는 문제들의 집합입니다. 현재 P와 PSPACE가 동일한지에 대한 질문은 큰 미해결 문제 중 하나입니다.

P는 다항 시간 내에 해결할 수 있는 결정 문제의 집합입니다.
PSPACE는 다항 공간 내에 해결할 수 있는 결정 문제의 집합입니다.
증명은 P 내의 문제가 항상 PSPACE 내에도 있음을 보이는 것입니다. 이는 문제를 해결하는 데 필요한 시간이 항상 그 문제를 해결하는 데 필요한 공간보다 많거나 같기 때문입니다.
열린 문제는 현재 아직 해결되지 않은 미해결 문제를 나타냅니다. P와 PSPACE가 동일한지, 그리고 NP와 PSPACE 사이의 관계에 대한 정확한 관계는 아직 알려져 있지 않습니다.