(계산적인computational) 문제 - 명확하게 정의된(stated) 입력/출력 [easy?(쉬운문제란?) hard?(어려운 문제란?) 기준(criterion/criteria)이란?]
인스턴스(Instance) 란?
여행하는 세일즈맨 문제 (Traveling Salesman Problem, TSP)
Input: an undirected graph G=(V, E), a positive real number (called traveling cost) assigned for each pair of distinct nodes in V, a positive real number B Output: yes if it is possible to start a node x and visit all other nodes exactly once and return to the starting node x in such a way that the summation of the total traveling costs is less than or equal to B, no otherwise
입력:
무방향 그래프 , 각기 다른 노드 쌍에 할당된 양의 실수 (여행 비용이라고 함), 양의 실수
출력:
만약 노드 에서 시작하여 모든 다른 노드를 딱 한 번 방문하고 시작한 노드 로 돌아오는 경로의 전체 여행 비용의 합이 이하라면 "예", 그렇지 않으면 "아니오"
"쉬운 문제"와 "어려운 문제"의 구분은 계산 이론(computational theory)에서 중요한 역할을 합니다. 계산 문제의 난이도는 주로 다음의 기준에 따라 분류됩니다.
1. **결정 문제의 해결 가능성(Decidability)**:
- **Decidable(결정 가능)**: 주어진 문제를 해결하는 알고리즘이 존재하며, 유한한 시간 안에 정답이나 결과를 제공할 수 있습니다.
- **Undecidable(결정 불가능)**: 주어진 문제를 해결하는 알고리즘이 존재하지 않습니다. 예를 들면, 튜링 기계가 주어진 입력에 대해 멈출지 안 멈출지를 결정하는 "Halting Problem"이 있습니다.
2. **시간 복잡도(Time Complexity)**:
- **P(다항 시간)**: 문제를 해결하는 알고리즘이 다항 시간 복잡도를 가진 경우. 이러한 문제들은 일반적으로 '쉽다'고 생각됩니다.
- **NP(비다항 시간)**: 주어진 해결책이 올바른지 다항 시간 내에 확인할 수 있지만, 해결책을 찾는 데 다항 시간이 걸릴지는 알려져 있지 않습니다.
3. **공간 복잡도(Space Complexity)**: 문제를 해결하는 데 필요한 메모리 양에 따라 분류합니다.
4. **NP-Complete와 NP-Hard**:
- **NP-Complete(비다항 완전)**: NP 클래스에 속하는 문제들 중에서 가장 어려운 문제들입니다. 만약 NP-Complete 문제 중 하나를 다항 시간 내에 해결할 수 있는 알고리즘이 있다면, 모든 NP 문제들도 다항 시간 안에 해결될 수 있다고 여겨집니다.
- **NP-Hard(비다항 어려움)**: NP-Complete 문제보다 더 어려울 수 있는 문제들입니다. 하지만, 정확한 해결책의 존재 여부는 알려져 있지 않습니다.
"쉬운 문제"와 "어려운 문제"의 구분은 많은 요소에 따라 달라질 수 있습니다. 이론적인 관점에서 볼 때, 문제의 복잡도와 해결 가능성에 따라 문제의 난이도를 분류합니다. 하지만 실제 애플리케이션에서는 구체적인 문제의 세부 사항, 사용 가능한 자원, 해결에 필요한 시간 등 여러 요소가 고려될 수 있습니다.
여행하는 세일즈맨 문제는 최적화 및 이론 컴퓨터 과학 분야에서의 고전 문제입니다. 모든 도시를 정확히 한 번만 방문하고 시작 도시로 돌아오는 가장 짧은 경로를 찾는 것이 목표입니다.
입력:
- 무방향 그래프
- 는 노드의 집합입니다 (TSP의 맥락에서는 도시를 나타냅니다).
- 는 노드들을 연결하는 간선의 집합입니다.
- 내의 각기 다른 두 노드 쌍에 대해 할당된 양의 실수.
- 이 숫자는 두 노드 사이의 여행 비용을 나타냅니다.
- 양의 실수 .
- 이것은 전체 경로에 허용된 예산 또는 최대 비용을 나타냅니다.
출력:
- 가능한 경우의 출력은 "yes"입니다:
- 노드 에서 시작합니다.
- 의 모든 다른 노드를 정확히 한 번만 방문합니다.
- 시작 노드 로 돌아옵니다.
- 이 경로의 여행 비용 합계가 이하인지 확인합니다.
- 이러한 경로가 가능하지 않은 경우 출력은 "no"입니다.
이미지에서 주어진 예시들:
첫 번째 그래프 에서 는 6입니다. 여기에서 가능한 경로는 a -> c -> b -> a로, 여행 비용은 2 + 3 + 1 = 6으로 값과 같습니다. 따라서 답은 "yes"입니다.
두 번째 그래프 에서 는 8입니다. 그러나 주어진 그래프에서 모든 도시를 방문하고 시작 도시로 돌아오는 경로의 최소 비용은 8보다 큽니다. (a->b->c->d->a-> = 2 + 3 + 4 + 1 = 10....) 따라서 답은 "no"입니다.
<이 문제는 NP-어려움(NP-hard)으로 알려져 있습니다. 이는 이 문제에 대한 다항 시간 해결책이 알려져 있지 않음을 의미합니다 (P ≠ NP라고 가정할 때). 따라서 큰 인스턴스의 경우 계산적으로 도전적입니다.> --- 맞는지 확인해볼것!
여행하는 세일즈맨 문제 (Traveling Salesman Problem, TSP)
노드의 수가 n일 경우, n! = n * (n-1) * ... * 1 가능성이 있다. 이러한 모든 가능성을 검사함으로써 문제를 해결하는 것이 가능하다 - "무차별 대입"(brute force) 방법. 만약 n이 크면 이 방법은 다루기 힘들다.
이 문제를 "효율적으로" 해결하는 방법이 있을까?
- "효율적인 방법"이라는 것은 무엇을 의미하는가? (최악의 상황에서 )입력 크기의 다항식으로 표현된 수행 단계 수: Cobham-Edmonds의 논문
- 지금까지는, 우리는 확실하게 모른다. 효율적인 방법이 존재하지 않는 것처럼 보이지만, 아직 증명되지 않았다.
제시된 텍스트는 "여행하는 세일즈맨 문제"와 관련된 문제의 복잡성에 대한 설명입니다.
- 여행하는 세일즈맨 문제를 해결하는 하나의 방법은 무차별 대입 방법으로, 모든 가능한 경로를 검사하는 것입니다. n개의 노드가 있을 때 n!의 모든 가능한 경로를 확인해야 하므로, n이 큰 경우 이 방법은 계산이 매우 복잡해집니다.
- 이 문제를 효율적으로 해결하는 방법이 있는지는 아직 알려져 있지 않습니다. 효율적인 알고리즘이라는 것은 해당 문제를 해결하는 데 필요한 단계 수가 입력 크기의 다항식 시간 내에 끝날 수 있는 알고리즘을 의미합니다. 이러한 효율성의 정의는 Cobham-Edmonds 씨의 논문에서 제시된 것입니다.
- 현재까지는 효율적인 방법으로 이 문제를 해결할 수 있는지 확실하게 알려진 바 없습니다. 일반적으로는 효율적인 방법이 존재하지 않는다고 생각되지만, 이것이 정확한지는 아직 증명되지 않았습니다.
분할 문제(Partition problem)
입력: 양의 정수로 구성된 비어 있지 않은 집합 A와 양의 정수 x
출력: A의 부분집합 중 합이 x와 같은 부분집합이 있으면 yes 그렇지 않으면 no
예:
A = {1, 4, 10, 5, 9, 12, 3}, x = 7 [yes 인스턴스] yes (4+3=7)
A = {1, 2, 3, 4, 10}, x = 100 [no 인스턴스] no ( 1+2+3+4+10 = 20 )
알려진 사실:
1. 무한히 많은 (사실, 가산할 수 없을 만큼 많은 uncountable) 계산 문제가 있다.
==> computational problem : infinitely,uncountable
2. 무한히 많지만, 가산 가능한(countable) 알고리즘이 있다.
==> algorithm : infinitely, countable
3. (그러므로) 계산할 수 없는(uncomputable) 문제들이 있다.
==> uncomputable problem
설명: 제시된 텍스트는 "분할 문제"와 관련된 문제의 복잡성 및 기본 개념에 대한 설명입니다.
- 분할 문제는 주어진 양의 정수 집합에서 특정 값 x와 동일한 합을 가진 부분집합을 찾는 문제입니다. 예를 들어, 집합 A와 숫자 x가 주어질 때, A의 부분집합 중에서 합이 x와 같은 것이 있으면 "yes"를 반환하고, 그렇지 않으면 "no"를 반환합니다.
- 알려진 사실은 계산 이론의 기본 개념을 설명합니다. 이 개념에 따르면, 가능한 계산 문제는 무한하며, 이 중에서는 가산할 수 없는 문제들도 있습니다. 반면에, 알고리즘은 무한하지만 가산 가능하다는 것을 나타냅니다. 이 두 가지 사실을 결합하면, 계산할 수 없는 문제들이 존재한다는 결론을 얻을 수 있습니다. 이는 모든 문제에 대해 효율적인 알고리즘이 존재하지 않음을 의미합니다.
여행 판매원 문제와 분할 문제의 구조적 유사성
두 문제 모두 가능성(possibilities) 중에서 해결책(solution)을 "검색"(searching)하는 것을 요구합니다.
(문제의 크기가 커질수록, 검색 공간searching space이 다루기 어려워집니다.)
[반면]
우리에게 올바른(correct) 해결책이 주어지면 (증명서certificate라고 불림 또는 yes certificate)
그것이 정말 맞는지 확인하는 것은 상대적으로 쉽습니다.
예시 문제)
증명서: a, c, b, a
이게 정말로 올바른 것인지 확인하려면, 여행 비용의 총 합이 6 이하인지를 확인해야 합니다. 모든 관련 여행 비용을 더해야 하는데, 이것은 "쉽게" 수행될 수 있습니다. 또한, a, c, b, a가 시작 노드를 제외하고 반복 없이 노드의 올바른 순열인지를 쉽게 확인할 수 있습니다.
설명:
여행 판매원 문제와 분할 문제는 계산 이론에서 유명한 NP 문제입니다. 이 텍스트는 이 두 문제의 구조적 유사성에 관한 설명입니다.
- 검색 공간: 두 문제 모두 가능한 해결책을 "검색"하는 과정이 필요하며, 문제의 크기가 커짐에 따라 검색 공간이 커져서 문제를 해결하기 어려워질 수 있습니다.
- 증명서 (Certificate): 해결책의 정당성을 확인하는 것을 의미합니다. 여행 판매원 문제에서는 주어진 경로가 주어진 비용 이하로 도시를 방문할 수 있는지를 쉽게 확인할 수 있어야 합니다. 즉, 주어진 해결책이 정확한지를 검증하는 과정이 상대적으로 간단하다는 것을 의미합니다.
결론적으로, 두 문제 모두 해결책을 찾는 과정은 어려울 수 있지만, 한 번 해결책이 주어지면 그것의 정당성을 확인하는 것은 비교적 쉽다는 특성을 공유합니다.
먼저, 제공된 그림은 여행 판매원 문제의 예시를 보여줍니다. 그림을 기반으로 설명하겠습니다.
그림의 설명:
- 노드와 간선: 그래프에는 세 개의 노드 (a, b, c)와 그 사이의 간선이 표시되어 있습니다. 각 간선에는 두 노드 사이의 여행 비용이 표시되어 있습니다.
- a와 b 사이: 1
- b와 c 사이: 3
- a와 c 사이: 2
- 목표: 주어진 예산 B (이 경우 6) 이내에서 모든 노드를 정확히 한 번 방문하고 시작점으로 돌아오는 경로를 찾는 것입니다.
- 해결책 (증명서): a, c, b, a는 노드 a에서 시작하여 c와 b를 거쳐 다시 a로 돌아오는 경로를 나타냅니다. 이 경로의 총 여행 비용은 2 (a에서 c까지) + 3 (c에서 b까지) + 1 (b에서 a까지) = 6으로, 주어진 예산 6 이내입니다. 따라서 이 경로는 올바른 해결책이 됩니다.
여행 판매원 문제와 분할 문제는 모두 가능한 해결책을 "검색"하는 과정이 필요하다는 구조적 유사성을 갖습니다. 하지만, 올바른 해결책 (즉, 증명서)이 주어지면, 그 해결책의 정당성을 쉽게 확인할 수 있습니다. 예를 들어, 여행 판매원 문제에서 주어진 경로가 예산 내에서 모든 도시를 방문할 수 있는지 확인하는 것은 각 간선의 비용을 더하는 것만큼 간단합니다.