[Algorithms] NP-Completness

NP-completeness는 계산 복잡도 이론의 개념이다.

1. 복잡도 이론의 기본 개념
먼저, 문제를 풀 때 알고리즘의 효율성을 평가하는 데 사용되는 두 가지 주요 분류는 다음과 같다 :
P 문제: 주어진 입력에 대해 다항 시간(polynomial time) 내에 해결할 수 있는 문제이다. 즉, 어떤 문제를 풀기 위한 알고리즘이 입력 크기에 대해 다항적인 시간 내에 종료되면 그 문제는 P 문제에 속한다고 볼 수 있다. Linear search(n), Binary search(log n) 등이 이에 속한다.
NP 문제: 주어진 입력에 대해 해답을 검증할 수 있는 문제이다. 즉, 어떤 후보 해답이 주어졌을 때, 그것이 문제의 해답이 맞는지 다항 시간 내에 검증할 수 있다면 그 문제는 NP 문제에 속한다.

2. P와 NP
P 문제는 우리가 알고리즘을 통해 효율적으로 풀 수 있는 문제들이다.
NP 문제는 해답을 검증할 수 있는 문제들이지만, 반드시 다항 시간 내에 풀 수 있는 것은 아니다. 즉, 해답을 찾는 과정이 다항 시간 내에 이루어지지 않을 수 있지만, 해답이 주어졌을 때 그것을 검증하는 과정은 다항 시간 내에 할 수 있다.

3. NP-완전성(NP-completeness)
NP-completeness는 NP 문제 중에서도 특히 어려운 문제들을 분류하는 개념이다. NP-완전한 문제는 다음 두 가지 조건을 만족한다.
NP에 속한다: 문제 자체는 NP 문제이며 즉, 해답을 검증하는 것은 다항 시간 내에 가능하다.
모든 NP 문제는 다항 시간 내에 이 문제로 변환할 수 있다: 이는 다른 모든 NP 문제들이 이 문제로 다항 시간 내에 변환 가능하다는 뜻이다. 즉, NP-완전 문제를 해결할 수 있으면, NP에 속하는 모든 문제를 해결할 수 있다는 것이다.

4. NP-완전 문제의 예시
TSP, Traveling Salesman Problem : 주어진 도시들을 한 번씩만 방문하고 다시 출발점으로 돌아오는 가장 짧은 경로를 찾는 문제
Subset Sum Problem : 주어진 숫자들 중 일부를 고를 때, 그 합이 특정 값이 되는지를 확인하는 문제
Knapsack Problem : 제한된 용량의 배낭에 다양한 물건들을 담을 때, 최대 가치를 얻는 방법을 찾는 문제
이 문제들은 모두 NP-완전 문제로 분류된다.

5. NP-완전 문제의 특성
해답을 찾는 것이 매우 어렵다: NP-완전 문제는 주어진 입력에 대해 효율적인 알고리즘을 찾는 것이 매우 어렵다. (따라서 다항 시간 내에 풀 수 있는 알고리즘이 존재하지 않을 가능성이 큼)
해답을 검증하는 것은 쉬울 수 있다: 문제의 해답이 주어졌을 때, 그것이 맞는지 검증하는 과정은 다항 시간 내에 가능할 수 있다. 예를 들어, TSP에서 주어진 경로가 최단 경로인지 검증하는 것은 다항 시간 내에 할 수 있다.
다른 NP 문제로의 변환: 어떤 문제를 해결할 수 있다면, 이를 통해 다른 NP 문제도 풀 수 있게 된다. NP-완전 문제는 변환 가능성을 통해 모든 NP 문제를 대표할 수 있으며 , NP-완전 문제를 해결할 수 있으면 다른 모든 NP 문제도 해결할 수 있다.

6. P = NP 문제
P = NP 문제는 미해결 문제로, P 문제와 NP 문제가 같은 집합에 속하는지, 즉 모든 NP 문제는 다항 시간 내에 풀 수 있는 문제(P 문제)로 해결될 수 있는지를 묻는 문제이다.
P = NP가 성립한다면, 모든 NP 문제는 다항 시간 내에 해결할 수 있다는 것이므로, NP-완전 문제들도 다항 시간 내에 해결할 수 있다는 의미가 됨
하지만 P ≠ NP가 성립한다면, 일부 NP 문제는 다항 시간 내에 해결할 수 없다는 뜻이 됨. 현재까지 P = NP가 성립하는지 여부는 밝혀지지 않음.

7. NP-완전 문제 해결의 중요성
NP-완전 문제를 해결하는 방법이 발견된다면, 다른 모든 NP 문제도 해결할 수 있기 때문에, 매우 중요한 문제로 여겨진다. 하지만 현재로서는 다항 시간 알고리즘이 없다고 생각되며,
대부분의 NP-완전 문제는 Brute Force(모든 경우의 수를 탐색하는 방식)나 근사 알고리즘을 통해 해결함.


ps. 부울 논리 표현식에 변수들에 대한 참거짓을 할당해 전체 식을 참으로 만들 수 있는가? 라는 명제 자체가 이해가 잘 되지 않았음 따로 공부해야 할 것


ㅋㅋㅋㅋㅋㅋ
아 이거 시험문제 하나도 안 나옴