NP-Complete

3-SAT

3-충족 가능성 문제(3-SAT, Boolean satisfiability problem)는 NP-완전의 대표주자이고 모든 문제 환원의 기준이다. 이 문제는 참 또는 거짓의 진리 값을 가질 수 있는 3개의 문자 또는 변수 p,q,r 이 있다. 그리고 논리합으로 연결된 절 몇 개가 논리곱으로 구성된 부울 수식 f가 참이 되도록 문자의 진리 값을 구할 수 있는가를 묻는다.

Hamiltonian Path / Cycle

Hamiltonian Path: 그래프의 모든 정점을 한번씩 방문하는 알고리즘
Hamiltonian Cycle: 시작점과 끝점이 동일한 헤밀턴 경로

Graph Coloring

그래프의 각 정점에 같은 색깔이 인접하지 않게 칠하는 방법이다. 이것으로 그래프의 불변성을 정의할 수 있다.

Vertex Cover / Independent Set / Clique

Vertex Cover: 선택한 정점들이 모든 정점들과 연결되어있다. 독립셋과 동치이다. NP의 다항시간 해답 검증이 직관적이다.
Independent Set: 정점이 서로 연결되지 않는 그래프
Clique: 부분그래프이면서 임의의 두노드가 서로 연결되어있는 것으로 정의된다. 독립셋과 동치이다.

Longest Path

주어진 가중치 그래프 G=(V,E)에서 시작점 s에서 도착점 t까지의 가장 긴 경로를 찾는 문제

Traveling Salesman Problem

주어진 가중치 그래프 G=(V,E)에서 한 점에서 출발해 다른 모든 점들을 1번씩만 방문하고 다시 시작점으로 돌아오는 경로 중 최단 경로를 찾는 문제

Set Cover ↔ Hitting Set

Set Cover: 원소들의 집합 U와 부분 집합들의 모임 S가 주어졌을 때, 합집합이 U와 같은 S의 가장 작은 부분 집합을 구하는 문제. 모든 미완성 퍼즐을 완성하기 위해 가장 적은 수의 퍼즐을 찾아야 하는 것.
Hitting Set: 원소들의 집합 U와 부분 집합들의 모임 S가 주어졌을 때, S의 모든 부분 집합과 교차하는 U의 가장 작은 부분 집합을 찾는 문제. 모든 미완성 퍼즐을 완성하는 데 사용할 수 있는 퍼즐 조각의 가장 적은 개수를 찾아야 한다.
설정된 커버 솔루션이 있는 경우, 선택한 세트 내의 요소만 취하면 쉽게 타격 세트를 식별할 수 있다. 반대로, 타격 세트가 있는 경우 타격 세트에서 하나 이상의 요소를 포함하는 모든 세트를 선택하여 세트 커버를 구성할 수 있다. 이 두 문제는 단지 원소와 집합을 덮거나 맞추는 것에 대한 같은 질문을 묻는 다른 방식일 뿐이다.

Bin Packing / Scheduling

크기가 정해진 아이템들을, 용량이 제한된 최소 개수의 박스에 나눠 담는 문제로, 조합 최적화를 요구하며 NP-완전이다. 아이템을 한번 배정하고 난뒤 무를수 없다. k는 미리 볼 수 있는 값의 수이다. 0~무한 까지 할당 가능하고 offline 일때 k는 무한이다.
- 아이템 리스트 (4개만) [0.4, 0.6, 0.5, 0.5] , 빈 용량: 1
Lookahead = 0 (First Fit)
1. 0.4 → 새 빈 [0.4] , 2. 0.6 → 첫 번째 빈(0.4) → OK → [1.0] , 3. 0.5 → 새 빈 [0.5] , 0.5 → 두 번째 빈(0.5) → OK → [1.0] 2개의 빈 사용
Lookahead = 1
1. 0.4 (다음: 0.6) → 둘이 합쳐서 1.0 만들 수 있으므로 새 빈 [0.4] , 2. 0.6 → 첫 번째 빈에 넣음 → [1.0] , 3. 0.5 (다음: 0.5) → 새 빈 [0.5] , 4. 0.5 → 두 번째 빈에 넣음 → [1.0] 2개의 빈 사용
Lookahead = ∞ (Offline 최적)
전체 조합: 0.4 + 0.6 = 1.0 , 0.5 + 0.5 = 1.0 2개의 빈 사용

ILP / 0-1 ILP