All
NP-완전 문제
NP-완전 문제란, 다음 두 조건을 모두 만족하는 판정 문제다:
1.
자기 자신이 클래스 NP에 속함
2.
NP에 속하는 모든 문제를 다항 시간 안에 이 문제로 변환할 수 있음
즉, "NP에서 가장 어렵다고 여겨지는 문제"들. 하나라도 다항 시간에 풀 수 있다면, NP 전체가 다항 시간에 풀릴 수 있음 → P = NP
튜링 기계 Turing machine
•
컴퓨터라는 개념이 나오기 전에 수학자 앨런 튜링이 제안한, 가장 단순한 컴퓨터 모델
•
우리가 생각하는 컴퓨터의 기본 동작을 흉내 낼 수 있음
•
구성요소: 테이프, 기호, 헤드, 상태, 규칙
결정론적 튜링 기계 (DTM, 클래스 P)
•
매 순간, 해야 할 행동이 단 하나로 정해져 있음
•
지금 상태와 입력 기호에 따라 명령이 딱 하나 존재
비결정론적 튜링 기계 (NTM, 클래스 NP)
•
매 순간, 할 수 있는 행동이 여러 개 있을 수 있음
•
마치 모든 경우를 동시에 시도하는 "병렬 우주" 같은 개념
•
현실에 존재하진 않지만 이론적으로 “빠르게 정답을 찾을 수 있다면?” 가정함
클래스 P
•
결정론적 튜링 기계가 다항 시간 내에 풀 수 있는 문제들
•
현실적인 컴퓨터가 빠르게 풀 수 있는 문제들
•
입력크기를 n이라고 할때 수행 시간이 같이 다항식 형태로 증가하는 문제
•
예시 문제:
◦
정렬, 최소값 찾기, BFS/DFS 기반 탐색 문제 등
클래스 NP
•
비결정론적 튜링 기계가 다항 시간 내에 풀 수 있는 문제들
•
정답이 주어졌을 때 검증은 빠르지만, 직접 푸는 건 어려운 문제들의 모임
•
정답이 맞는지는 다항 시간 안에 확인 가능하지만, 정답을 찾으려면 경우의 수가 폭발적일 수 있음
•
예시 문제:
◦
외판원 문제: “이 경로가 최단 경로냐?” → 주어진 경로 확인은 빠름
◦
그래프 클리크: “이 k개의 노드가 완전 연결됐냐?” → 확인은 빠름
문제 변환 reduction
문제 Q를 문제 A로 변환하여, 문제 A의 알고리즘으로 문제 Q를 해결 가능하게 는 과정
정의
•
문제 Q의 입력을 문제 A의 입력 형식으로 변환
•
문제 A의 알고리즘으로 문제 A를 풀고
•
그 결과를 다시 문제 Q의 답으로 해석
다항 시간 변환
•
변환 자체가 입력 크기의 다항식 시간 안에 수행 가능해야 함
→ 현실적으로 계산 가능한 범위
NP-완전 문제의 조건
문제 A가 NP-완전(NP-Complete)이 되려면 다음 두 가지를 만족해야 함:
1. 문제 A ∈ NP
•
비결정론적 튜링 기계로 다항 시간 안에 검증 가능한 문제여야 함
•
정답이 맞는지 빠르게 확인할 수 있는 문제
2. ∀ B ∈ NP에 대해, B ≤p A
•
NP 안의 모든 문제 B를 문제 A로 다항 시간 안에 변환 가능해야 함
•
문제 A가 NP 전체 중 가장 어려운 문제들과 최소한 같은 수준이어야 함
NP-완전 문제 예
•
CNF 만족성
•
클리크 판정
•
버텍스 커버
•
해밀토니언 사이클
•
외판원
•
통 채우기 등등
근사 알고리즘
NP-하드 문제처럼 풀기 너무 어려운 최적화 문제를 다항 시간 안에 거의 최적에 가까운 해로 푸는 알고리즘
•
모든 NP-완전 문제는 NP-하드 문제임
•
클래스 NP에 속하는 모든 문제가 그 문제로 다항 시간에 변환되는 문제
주요 근사 알고리즘 예시
버텍스 커버 문제
•
문제: 그래프의 모든 간선을 적어도 한 번씩 덮는 최소 정점 집합 구하기
•
방법:
◦
간선을 하나 선택 → 양 끝 정점 모두 선택
◦
선택한 간선과 연결된 간선 제거 → 반복
•
성능:
◦
근사해는 최적해의 2배 이하
외판원 문제
•
문제: 모든 도시를 한 번씩 방문하고 다시 출발지로 돌아오는 최소 비용 경로 찾기
•
가정: 이동 비용이 삼각 부등식을 만족해야 함
•
방법:
◦
최소 신장 트리(MST) 구성
◦
MST 기반으로 DFS 순회 경로 생성
•
성능:
◦
근사해는 최적해의 2배 이하
통 채우기 문제
•
문제: 크기가 0~1인 물체을 가능한 적은 개수의 단위 크기 통에 채우기
•
전략들:
방법 | 설명 | 성능 (근사해 / 최적해 비율) |
최초적합 (First Fit) | 왼쪽부터 넣을 수 있는 첫 통에 넣음 | ≤ 1.7배 |
최선적합 (Best Fit) | 남는 공간이 가장 작은 통에 넣음 | ≤ 1.7배 |
감소순 최초적합 (FFD) | 물체 내림차순 정렬 + First Fit | ≤ 1.3배 |
감소순 최선적합 (BFD) | 물체 내림차순 정렬 + Best Fit | ≤ 1.3배 |