PATH를 결정하는 결정적 튜링 머신(dTM) M (= PATH를 결정하는 결정적 알고리즘) - 너비 우선 탐색(BFS)
PATH를 결정하는 결정적 튜링 머신(dTM) M (= PATH를 결정하는 결정적 알고리즘) - 너비 우선 탐색(BFS)
M은 다음과 같이 정의됩니다: "입력 (G, s, t)에 대하여, G는 시작 노드 s와 종료 노드 t를 가진 방향 그래프입니다:
- 노드 s에 표시를 합니다.
- 추가로 표시할 노드가 없을 때까지 아래 작업을 반복합니다:
- G의 모든 간선을 검사합니다. 만약 표시된 노드 a에서 표시되지 않은 노드 b로 가는 간선 (a, b)이 발견되면, 노드 b에 표시를 합니다.
- 만약 t가 표시되어 있으면, '수락'합니다. 그렇지 않으면 '거절'합니다."
s는 표시됨(marked)
(s,a), (a,b), (a,t), (b,s), (b,t) – a 표시(mark)
(a,b), (a,t), (b,s), (b,t) – b 표시, t 표시
t가 표시되었으므로 수락
s는 표시됨(marked)
(s,a), (a,b), (b,s), (t,a), (t,b) – a 표시
(a,b), (b,s), (t,a), (t,b) – b 표시
t가 표시되지 않았으므로 거부
단계 수 - 입력 그래프의 크기 O(=O(|V| + |E|)) 따라서, PATH는 P의 구성원입니다 기본적으로, 표시된 노드에서 표시되지 않은 노드로의 가장자리는 초기 "표시된" 노드 s와 함께 반복적으로 스캔됩니다.
이 텍스트는 너비 우선 탐색(BFS) 알고리즘을 사용하여 PATH 문제를 결정하는 결정적 튜링 머신에 대한 설명입니다.
- 첫 번째 예에서는 노드 s에서 t까지의 경로가 있음을 확인하고, BFS를 사용하여 해당 경로를 찾습니다. 처음에는 노드 s만 표시됩니다. 그 다음 각 단계에서 BFS는 현재 표시된 노드에서 직접 연결된 노드를 표시합니다. 이 예에서는 노드 a, b, t가 순차적으로 표시되며, t가 표시되면 해당 그래프에서 s에서 t까지의 경로가 있다는 것을 알 수 있습니다.
- 두 번째 예에서는 s에서 t까지의 경로가 없습니다. BFS를 사용하여 탐색한 결과, 노드 t는 표시되지 않습니다. 따라서 s에서 t까지의 경로가 없다고 결론지을 수 있습니다.
마지막 부분은 BFS의 성능에 관한 것입니다. BFS는 그래프의 모든 노드와 간선을 최대 한 번씩만 방문하기 때문에, 그 성능은 그래프의 크기에 선형적이다. 따라서 이 알고리즘은 그래프의 크기에 따라 다항 시간 내에 실행됩니다.
이는 PATH가 P 클래스에 속한다는 것을 의미합니다.
여기서 P 클래스는 다항 시간 내에 결정적 튜링 머신으로 해결될 수 있는 문제들의 집합을 의미합니다.
먼저, 텍스트의 내용은 "PATH"라는 문제를 결정하는 결정적 튜링 머신(deterministic Turing Machine, dTM) M에 대한 것입니다. 여기서 사용된 알고리즘은 너비 우선 탐색(BFS, Breadth First Search)이며, 주어진 그래프에서 시작 노드 s에서 종료 노드 t로의 경로를 찾는 것이 목적입니다.
주어진 이미지에는 두 개의 그래프 예시가 있습니다: "yes instance"와 "no instance".
- "yes instance"에서는 s에서 t까지의 경로가 존재합니다.
- "no instance"에서는 s에서 t까지의 경로가 존재하지 않습니다.
BFS 알고리즘은 다음과 같이 동작합니다:
- 시작 노드 s를 표시합니다.
- 모든 노드가 표시될 때까지 다음 작업을 반복합니다:
- 현재 표시된 노드에서 직접 연결된 노드를 표시합니다.
- 만약 종료 노드 t가 표시되면 "accept", 그렇지 않으면 "reject"합니다.
주어진 텍스트 예시를 보면:
- 첫 번째 예시에서는 BFS 알고리즘을 사용하여 노드 s에서 시작하여 노드 t까지의 경로를 찾을 수 있습니다. 따라서 결과는 "accept"입니다.
- 두 번째 예시에서는 BFS 알고리즘을 사용하였지만 노드 t가 표시되지 않습니다. 따라서 결과는 "reject"입니다.
마지막으로, BFS의 성능은 그래프의 크기와 관련이 있습니다. BFS는 그래프의 모든 노드와 간선을 최대 한 번씩만 방문하기 때문에, 그 성능은 그래프의 크기에 선형적입니다. 따라서 이 알고리즘은 그래프의 크기에 따라 다항 시간 내에 실행됩니다. 이는 "PATH"가 P 클래스에 속한다는 것을 의미합니다.
P 클래스는 다항 시간 내에 결정적 튜링 머신으로 해결될 수 있는 문제들의 집합을 나타냅니다.
NP의 정의 (검증자verifier의 관점에서)
검증자(verifier)는 알고리즘입니다.
우리에게는 결정되어야 하는(need to be decided) 언어 L이 주어집니다 - 결정(decision) 문제입니다.
다항 시간 알고리즘. 구체적으로, 언어 L은 NP에 속한다는 것은 그것이 두 입력 다항 시간 알고리즘 A와 상수 c가 존재할 때만 가능하다는 것을 의미합니다.
L은 {x ∈ {0,1}* : y라는 증명서certificate가 존재하며 |y| = O(|x|^c)이고 A(x,y) = 1인 경우}로 정의됩니다.
우리는 알고리즘 A가 다항 시간 내에 언어 L을 검증한다고 말합니다.
y는 증명서certificate (또는 증인witness)로 불립니다.
A의 실행 시간은 "x"의 관점에서 주어집니다.( "y"가 아니다. 그렇지만...)
L이 NP의 구성원이라면 "존재"(exists)합니다... (존재하는 것(existence)이 중요합니다)
이 내용은 계산 복잡도 이론에서 NP 클래스를 정의하는 방법에 관한 것입니다.
- NP: NP는 문제의 해결책이 주어진 경우 그 해결책이 올바른지 다항 시간 내에 검증될 수 있는 결정 문제들의 집합입니다.
- 검증자(Verifier): 주어진 문제의 해결책이 올바른지 확인하는 알고리즘입니다.
- 언어 L: 결정 문제를 나타내는 집합입니다. 예를 들어, 어떤 그래프에서 특정한 속성(예: 해밀턴 순환)을 가진 경로가 있는지 여부와 같은 문제들을 나타낼 수 있습니다.
- 증명서(Certificate) 또는 증인(Witness): 주어진 문제의 해결책입니다. 이 증명서가 주어졌을 때 검증자는 다항 시간 안에 그 해결책이 올바른지 확인할 수 있어야 합니다.
결론적으로, NP 클래스의 문제는 그 해결책이 주어진 경우 다항 시간 내에 그 해결책이 올바른지 확인할 수 있어야 합니다. 이러한 검증 과정이 검증자에 의해 이루어집니다.
the runtime of A is given in terms of “x” (NOT by “y”, but…):
- 이 문장은 알고리즘 A의 실행 시간이 입력 "x"의 크기에 의해 결정되며 "y" (증명서나 증인)의 크기에 의해 결정되지 않는다는 것을 의미합니다. NP에 속하는 문제의 경우, 주어진 해를 검증하는 데 필요한 시간은 입력 "x"의 크기에 비례하며, 증명서 "y"의 크기에는 비례하지 않습니다.
L is a member of NP iff there “EXISTS”… (existence is important):
- 언어 L(또는 문제)이 NP 클래스에 속하려면, 주어진 모든 "yes" 인스턴스에 대해, 그것이 "yes"임을 증명하는 증명서 "y"가 존재해야 합니다. 여기서 "존재"하는 것은 중요하며, 이 증명서를 통해 주어진 해가 올바른지 다항 시간 내에 검증할 수 있어야 합니다.
비결정적 다항 시간 알고리즘의 관점에서 본 NP의 정의
N = "길이 n의 입력 w에 대하여:
- 최대 길이 n^k의 문자열 c를 비결정적으로 선택한다.
- 입력 (w, c)에 대해 V를 실행한다.
- V가 수락하면, 수락한다; 그렇지 않으면, 거절한다."
V = "w와 c가 문자열인 입력 (w, c)에 대하여:
- w의 입력에 대해 N을 시뮬레이션하며, c의 각 기호를 각 단계에서 만들 비결정적 선택의 설명으로 처리한다 (정리 3.16의 증명에서처럼).
- N의 계산의 이 분기가 수락하면, 수락한다; 그렇지 않으면, 거절한다."
N이 존재한다면, V는 구성될 수 있다.
V가 존재한다면, N은 구성될 수 있다.
다시 말해서, 이 두 정의는 동등하다!
여기서 N과 V는 알고리즘이나 함수와 같은 연산을 나타냅니다. N은 주어진 입력 w에 대해 비결정적으로 선택된 문자열 c를 사용하여 V를 실행하고, V의 결과를 기반으로 결정을 내립니다. V는 비결정적 선택을 시뮬레이션하여 N의 동작을 모방합니다. 이러한 설명은 NP와 그 정의에 관한 이론적 내용과 관련이 있습니다. NP 문제는 솔루션을 검증하는 것이 다항 시간 내에 가능하다는 것을 의미하며, 위의 N과 V 정의는 그러한 속성을 가진 알고리즘을 설명하는 데 도움을 줍니다.
이 문장은 계산 복잡도 이론에서 NP의 두 가지 다른 정의가 서로 동등하다는 것을 의미합니다. "N"은 비결정적 다항 시간 알고리즘을 나타내며, 이는 문제의 솔루션을 "추측"하고 그것을 다항 시간 내에 확인할 수 있는 알고리즘을 의미합니다. 반면 "V"는 검증기를 나타내며, 이는 솔루션(증명서)이 주어진 경우 그것이 올바른지 다항 시간 내에 확인할 수 있는 알고리즘을 의미합니다.
이 두 정의는 서로 동등하다는 것이 밝혀져 있습니다. 즉, 비결정적 다항 시간 알고리즘이 문제의 솔루션을 추측하고 검증할 수 있다면, 그 문제에 대한 검증기가 반드시 존재한다는 것을 의미합니다. 반대로, 검증기가 존재한다면 해당 문제에 대한 비결정적 다항 시간 알고리즘이 반드시 존재한다는 것을 의미합니다.
N에서 V로: V가 w를 수락하는 최대 n^{k} 크기의 문자열 c가 존재하기 때문에, V는 입력이 (w, c)인 다항 시간 검증기로 작동할 수 있습니다. V의 동작은 c의 각 기호가 N의 시뮬레이션을 위해 어떤 방향으로 진행할지를 "안내"한다는 방식입니다.
V에서 N으로: 언어 L을 결정하는 다항 시간 검증기(V)가 있기 때문에, w와 함께 V에 주어질 때, 최대 n^{k} 크기의 "비결정적 선택" c가 V가 올바르게 작동하도록 보장됩니다.
이 두 알고리즘 N과 V는 비결정적 다항 시간(NP)의 개념을 나타내는데 사용되는 알고리즘입니다.
- N은 주어진 입력 w에 대해 특정 문자열 c를 비결정적으로 선택하고, 그 선택된 c와 함께 V를 실행합니다. 그 후, V의 결과에 따라 결정을 내립니다.
- V는 N의 계산을 시뮬레이션하여 동작합니다. 입력된 문자열 c의 각 기호는 N에서의 각 비결정적 선택을 나타내며, V는 그 선택들을 사용하여 N이 어떻게 동작할지 예측합니다.
간단히 말해, N과 V는 서로 상호 작용하며, V는 N의 비결정적 선택을 시뮬레이션하여 N이 어떻게 동작할지를 예측합니다. 이러한 알고리즘은 NP의 정의와 관련된 이론적 개념에서 중요한 역할을 합니다. NP 클래스의 문제는 솔루션을 검증하는 것이 다항 시간 내에 가능하다는 것을 의미하며, 이 N과 V의 정의는 그러한 속성을 가진 알고리즘을 설명하는 데 도움을 줍니다.
이 문장들은 NP 클래스에 속하는 문제의 정의와 관련되어 있습니다.
- N에서 V로: 이 부분은 비결정적 알고리즘 N과 다항 시간 검증기 V 사이의 관계를 설명합니다. N의 동작을 따라가며 w를 수락하는 문자열 c가 있다면, 이 문자열 c는 V가 w를 수락할지 여부를 결정하는 데 필요한 "증거" 또는 "증명" 역할을 합니다. V는 이 증거 c를 사용하여 N의 동작을 빠르게 시뮬레이션합니다.
- V에서 N으로: 이 부분은 다항 시간 검증기 V가 있을 때 비결정적 알고리즘 N을 구성하는 방법을 설명합니다. 언어 L을 결정하는 검증기 V가 주어지면, 비결정적 알고리즘 N은 V가 올바르게 작동할 수 있도록 w와 함께 필요한 증거 문자열 c를 선택합니다.
간단히 말해, 이 두 문장은 NP 문제의 특성에 따라 비결정적 알고리즘과 다항 시간 검증기 사이의 관계를 설명합니다. NP 문제는 솔루션(증거)을 검증하는 것이 다항 시간 내에 가능한 문제들로 정의됩니다.