번역: P vs NP 문제란 무엇인가? (나중에 자세히 다룰 것이지만...)
P: 효율적인 알고리즘이 존재하는 문제들의 집합
NP: 효율적인 검증 알고리즘이 존재하는 문제들의 집합, 여기서 검증 알고리즘은 두 개의 입력 X, Y를 받으며, X는 문제의 YES 인스턴스이고 Y는 증명서입니다.
P는 NP의 부분집합이지만... NP도 P의 부분집합인가? [그럴 가능성은 적지만, 아직 그 답을 모릅니다.]
설명: P vs NP 문제는 컴퓨터 과학에서 가장 중요하고 미해결된 문제 중 하나입니다.
- P: P 클래스에 속하는 문제들은 "다항 시간" 내에 해결할 수 있는 알고리즘이 존재한다는 것을 의미합니다. 다시 말해, 이러한 문제들은 충분히 큰 컴퓨터와 충분한 시간이 주어지면 풀 수 있습니다.
- NP: NP 클래스에 속하는 문제들은 어떤 해결책이 주어졌을 때, 그 해결책이 올바른지 아닌지를 "다항 시간" 내에 확인할 수 있는 알고리즘이 존재한다는 것을 의미합니다. 하지만 이 문제를 처음부터 다항 시간 내에 해결할 수 있는지는 알려져 있지 않습니다.
문제의 핵심은 P와 NP가 동일한지, 다른지에 대한 것입니다.
다시 말해, NP 문제 중 하나를 효율적으로 해결할 수 있는 알고리즘이 존재한다면, 모든 NP 문제를 효율적으로 해결할 수 있는 알고리즘이 존재한다는 것을 의미합니다. 하지만 현재로서는 이 문제에 대한 답을 아는 사람은 없습니다.
Traveling salesman 문제나 Partition 문제와 같은 구조적 특성을 가진 다른 문제들도 있나요?
- 네, NP에 있는 모든 문제들!
P vs NP 문제의 역사
- 고델이 폰 노이만에게 보낸 편지 (1956)
- 쿡과 레빈이 독립적으로 P vs NP 문제를 발표 (1970년대) 카프
- P vs NP를 포착하는 21개의 중요한 문제 (1970년대)
- 7개의 밀레니엄 문제 중 하나 - Clay 수학 연구소 (2000)
- ...
설명: P vs NP 문제는 컴퓨터 과학에서 가장 중요하고 아직 해결되지 않은 문제 중 하나입니다.
- Traveling salesman 문제나 Partition 문제와 같은 구조적 특성을 가진 문제들은 NP 클래스 안에 있습니다. 이러한 문제들은 해결책이 주어지면 그 해결책의 올바름을 다항 시간 내에 확인할 수 있습니다.
- 고델은 1956년 폰 노이만에게 이 문제에 관한 편지를 보냈습니다.
- 1970년대에 Stephen Cook와 Leonid Levin은 독립적으로 이 문제를 정의했습니다.
- 이후 Richard Karp는 P vs NP 문제의 본질을 잡아내는 21개의 NP-완전 문제를 제시했습니다.
- 2000년에는 Clay Mathematics Institute에서 제시한 7개의 천년 문제 중 하나로 P vs NP 문제를 선정했습니다. 천년 문제는 현재까지 해결되지 않은 주요 수학 문제들을 의미하며, 이 문제들 중 하나를 해결하면 백만 달러의 상금을 받게 됩니다.
최단 경로 문제 - 구조적 특성은?
다양한 버전들
- 단일 출발지(source) 단일 목적지(destination) 최단 경로
- 모든 쌍에 대한 최단 경로
- 단일 출발지(source) 최단 경로
...
시카고에서 피츠버그를 거쳐 뉴욕까지의 최단 경로를 고려하면
이는 다음으로 이루어져 있어야 합니다.
(1)시카고에서 피츠버그까지의 최단 경로
(2)피츠버그에서 뉴욕까지의 최단 경로
중요한 포인트는 무엇인가?
- 가능성이 많더라도 문제를 해결하기 위해 각 가능성을 확인할 필요가 없습니다.
- 문제의 구조적 특성을 활용하여 문제를 해결할 수 있습니다.
- [최적의 부분구조 특성 - 최적의 해결책은 원래 문제의 부분 문제들의 최적의 해결책으로 구성됩니다.]
설명: 최단 경로 문제는 그래프에서 두 노드 간의 가장 짧은 경로를 찾는 문제입니다. 이 문제에는 여러 버전이 있습니다, 예를 들어 단일 출발지에서 단일 목적지까지의 경로, 모든 노드 쌍 사이의 경로, 또는 단일 출발지에서 모든 다른 노드까지의 경로를 찾는 것입니다.
시카고에서 뉴욕까지의 경로를 찾을 때 피츠버그를 거치는 경우를 예로 들면, 이 경로는 시카고에서 피츠버그까지의 최단 경로와 피츠버그에서 뉴욕까지의 최단 경로로 나뉩니다.
이러한 관점은 최단 경로 문제가 '최적의 부분구조'라는 특성을 가진다는 것을 보여줍니다. 이 특성은 주어진 문제의 최적의 해결책이 그 문제의 부분 문제들의 최적의 해결책으로 구성되어 있음을 의미합니다. 이러한 구조적 특성을 이해하고 활용하면 문제를 훨씬 더 효율적으로 해결할 수 있습니다.
k-clique 문제
입력: 방향이 없는 그래프 G = (V, E), k로, k는 2 이상의 양의 정수입니다.
출력: G에 k-clique이 있으면 '예' 그렇지 않으면 '아니오'
k-클릭은 k개의 노드로 이루어진 방향이 없는 그래프이며, 각 노드 쌍이 에지(간선)로 연결되어 있습니다 (여기서 k는 2 이상이라고 가정합니다).
k-클릭 문제는 주어진 그래프 내에서 특정 크기(k)의 완전 연결된 부분 그래프(클릭)를 찾는 문제입니다. 클릭이란 그래프 내의 노드들 중 서로 모두 직접 연결된 노드의 집합을 의미합니다. k-클릭은 k개의 노드로 이루어진 클릭을 의미하며, 이때 각 노드 쌍 사이에는 에지(간선)가 있어야 합니다. 예를 들어, 3-클릭은 서로 모두 직접 연결된 3개의 노드로 이루어진 클릭을 의미합니다. k-클릭 문제의 목적은 주어진 그래프에 k 크기의 클릭이 존재하는지를 확인하는 것입니다.
- 첫 번째 그림은 "2-클릭"을 보여줍니다. 2개의 노드가 있으며, 이 두 노드 사이에는 간선(에지)이 있습니다. 이는 두 노드가 서로 연결되어 있음을 의미합니다.
- 두 번째 그림은 "3-클릭"을 나타냅니다. 3개의 노드가 있고, 각 노드 쌍 사이에는 간선이 있습니다. 이는 세 노드 모두 서로 연결되어 있음을 나타냅니다.
- 세 번째 그림은 "4-클릭"을 보여줍니다. 4개의 노드가 있으며, 모든 노드 쌍 사이에 간선이 있어서 완전 연결된 그래프를 형성합니다.
k-클릭 문제에서는 주어진 그래프 G에 k 크기의 클릭(즉, k개의 완전 연결된 노드)이 존재하는지를 확인하는 것이 목적입니다. 위의 그림들은 2-클릭, 3-클릭, 4-클릭이 어떻게 생겼는지를 간단하게 보여주는 예시입니다.
P = NP라면 어떻게 될까?
- 모든 것이 쉽게 계산될 수 있는 세계
- 질문: 이 세계는 우리가 살고 있는 세계와 다른가? 이 질문에 어떻게 대답할 수 있을까?
- (1) 이 문맥에서 '세계'란 무엇인가? 우리는 그것을 정의할 수 있을까?
- (2) 우리가 살고 있는 세계의 특성은 무엇인가? 계산( computation)은 무료(free)가 아니다.
- 즉, 항상 지불해야 할 비용이 있다. (시간, 공간, 네트워크 대역폭 등)
우리는 계산이 무료인 세계를 상상할 수 있을까?
P가 NP와 다르다는 것을 증명하는 방법
- 괴델: 수학은 모든 문제를 해결할 수 없다.
- "일부" 검색 문제들이 빠르게 해결될 수 없다는 것을 보이기 위해 비슷한 기술을 사용할 수 있을까?
어떤 의미에서, P 대 NP 문제는 최악의 상황에서 전체 검색 공간을 철저히 탐색하지 않고도 효과적으로 해결책을 찾을 수 있는지를 묻습니다.
양자역학이 도움이 될 수 있을까? [BQP - 양자 알고리즘으로 효과적으로 해결할 수 있는 문제들의 집합]
설명: 이 텍스트는 P와 NP, 두 계산 복잡도 클래스 간의 관계에 관한 질문을 다룹니다.
P는 다항 시간 내에 해결될 수 있는 결정 문제들의 집합이며, NP는 주어진 해결책의 정확성을 다항 시간 내에 검증할 수 있는 문제들의 집합입니다.
P와 NP의 관계는 컴퓨터 과학에서 중요한 미해결 문제 중 하나입니다.
텍스트는 P = NP일 경우 그런 세계의 특성에 대한 고찰을 제공합니다. 이러한 세계에서는 모든 계산 문제가 쉽게 해결될 수 있을 것입니다. 그러나 현실 세계에서는 계산에는 항상 비용이 발생합니다. 따라서 이런 세계는 현실 세계와는 다를 수 있습니다. <한번 찾아볼것>
또한, 괴델의 불완전성 정리와 같은 수학적 방법을 사용하여 P와 NP가 다르다는 것을 증명할 수 있는지, 그리고 양자역학이 이 문제의 해결에 도움이 될 수 있는지에 대한 질문도 제기됩니다.
독서 과제 - 제출은 필요하지 않습니다 (이 중 일부는 수업에서 설명하겠습니다)
논문 다운로드
Lance Fortnow에 의한 "P 대 NP 문제의 현황", 그리고
( http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf 에서 확인 가능)
(1) 섹션 2, P 대 NP 문제란 무엇인가?와 (2) 섹션 3, P = NP라면 어떨까?를 읽으십시오.
설명:
이 텍스트는 학생들에게 독서 과제를 지시하는 것입니다. 제출은 필요하지 않지만, 제공된 링크에서 Lance Fortnow이 작성한 "P 대 NP 문제의 현황"이라는 논문을 다운로드하라고 지시하고 있습니다. 학생들은 특히 논문의 두 섹션, 즉 "P 대 NP 문제란 무엇인가?"와 "P = NP라면 어떨까?"에 집중하여 읽어야 합니다. 이 내용의 일부는 수업 시간에 선생님에 의해 설명될 예정입니다.
<시간 나면 한번 볼것>
알고리즘이란 무엇인가?
튜링 머신의 정의로 시작해봅시다.
(다음 내용은 Borut Robic의 '계산 가능성 이론의 기초'라는 책에서 발췌한 것입니다)
텍스트는 "알고리즘이란 무엇인가?"라는 질문으로 시작하며, 튜링 머신의 정의를 통해 알고리즘에 대해 논의하려는 의도를 나타냅니다. 튜링 머신은 계산 이론의 핵심적인 개념 중 하나로, 모든 컴퓨터 알고리즘이 수행할 수 있는 작업을 수행할 수 있는 추상적 기계를 의미합니다.
이 그림은 기본적인 튜링 머신의 모델을 나타냅니다. 튜링 머신은 알고리즘과 계산 가능성을 표현하는 추상적인 기계로써 컴퓨터 과학에서 중요한 개념입니다.
그림의 요소는 다음과 같습니다:
- Control Unit (제어 유닛): 이 부분에는 'Turing program'이라는 레이블이 붙어 있으며, 튜링 머신의 작동 방식을 제어하는 프로그램을 포함하고 있습니다.
- Tape (테이프): 무한한 길이의 테이프로, 여러 개의 칸(cell)으로 구성되어 있습니다. 각 칸에는 정보나 데이터를 기록할 수 있습니다.
- Window (창): 테이프 위에 움직이는 가독/기록 장치로, 현재 위치의 테이프 칸의 내용을 읽거나 변경할 수 있습니다.
이 튜링 머신의 기본 구성은 제어 유닛이 프로그램에 따라 테이프의 칸을 읽고, 그에 따라 다음 동작을 결정하게 됩니다. 튜링 머신은 이러한 간단한 구조를 통해 다양한 계산 문제를 해결할 수 있는 놀라운 능력을 가지고 있습니다.