[알고리즘] CH13. Class P, NP, NP-Complete Problems

Summary

• Class P: 해당 문제를 다항 시간에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합
• Class NP: 해당 문제를 해결하는 Non-deterministic 다항 시간 알고리즘이 존재하는 문제.
  • 어떤 certificate를 다항시간에 verification할 수 있으면, 그 문제는 class NP에 속함

 

Class P

• The set of decision problems that are polynomially bounded
• 해당 문제(P)를 다항시간에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합
  • 다항 시간: 시간 복잡도가 $O(n^k)$, k가 상수
• 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다.

 

Class NP

• The set of decision problems for which there is a polynomially bounded non-deterministic algorithm
• 다항 시간에 varification하는 알고리즘이 존재하는 decision problems의 집합
• * Nondeterministic algorithm: 동일한 입력에 대해 서로 다른 실행에서 다른 동작을 나타낼 수 있는 알고리즘

 

 

Problems와 Algorithms의 관계

• complexity of a problem(문제의 복잡성)은 문제를 해결할 수 있는 최적 알고리즘의 복잡성이다.
• 정렬되지 않은 배열에서 가장 큰 값 찾기 -> $\Omega(n)$ 
• 배열 정렬 -> $\Omega(nlogn)$

 

Optimization Problems vs Decision Problems

• Optimization Problems
  • 최적의 값을 찾는 문제
  • ex) Shortest-path problem: weighted graph가 주어지고, u에서 v까지 최소한의 cost으로 가는 경로 찾기
• Decision Problmes
  • yes or no로 대답
  • ex) graph와 k가 주어졌을 때, u에서 v까지 최대 k개 이하의 edges만 포함하는 경로가 존재하는가? 
  • optimization problem을 풀면 풀 수 있음
• Optimization problem이 decision problem보다 어렵(쉽지 않은) 문제이다.

 

Class P

• k가 상수일 때, T(n) = O($n^k$) -> polynomial time
• class P에 속하는 문제는 다항시간에 문제를 해결할 수 있는 알고리즘이 존재한다고 말한다.
• 다항 시간에 해결하는 알고리즘을 efficient or tractable or easy하다고 말한다.

 

 

Hard한 문제들

• 다항 시간에 문제를 해결할 알고리즘이 아직 없는 문제들 
  • ex) 0/1 Knapsack problem, traveling salesperson problem
• Undecidable problems
  • 컴퓨터로 해결할 수 없는 문제
  • solvable = decidable

 

 

0/1 knapsack problem

• Optimization problem: 도둑이 동굴에 있는 보물을 가져가려고 한다. 도둑은 가방이 있고, 가방에는 weight가 최대 w만큼만 담을 수 있다. 무게가 w가 넘지 않으면서 value가 최대가 되도록 보물을 가져가자.
• Decision problem: 무게가 w가 넘지 않으면서 value가 k 이상인 아이템들의 집합이 존재하는가?
  • w: positive integer
  • 동굴 - n개의 아이템

item index (i)	1	2	3	...	n
value ($v_i$)	$v_1$	$v_2$	$v_3$		$v_n$
weight ($w_i$)	$w_1$	$w_2$	$w_3$		$w_n$

• 조건:
  1. 아이템은 가져가거나 놓고 가야한다.
  2. 한 아이템을 일부분만 가져갈 순 없다. 다 가져가거나 안 가져가거나
  3. 한 아이템을 한 번만 가져갈 수 있다.
• Fractional kanpsack problem
  • Class P에 속하는 문제
  • 0/1 knapsack problem에서 한 아이템의 일부분을 가져갈 수 있다.
  • 다항 시간에 풀 수 있다.

 

 

Traveling Salesperson Problem (TSP)

• 입력으로 complete-weighted graph가 주어진다.
• Optimization problem: 비용을 최소화하면서 모든 정점들을 한번씩만 방문하는 simple cycle을 찾는 문제 
  • simple cycle: 첫 번째 정점과 마지막 정점만 동일하고 나머지 정점은 다른 path를 가진 cycle
• Decision problem: 모든 정점들을 한 번씩만 지나는 cost가 k보다 작은 simple cycle이 존재하는가?
  • Decision problem -> NP-Complete 문제

 

 

Non-Deterministic Polynoial Time: Class NP

• Class NP: 다항 시간에 varification하는 알고리즘이 존재하는 decision problems의 집합
  • Non-deterministic polynomial-time algorithm 존재
• Class P에 속하는 문제들은 Class NP에도 속한다.
• P = NP?
  • 문제의 입력(input)과 근거(certification, witness)가 주어졌을 때
  • P = NP인가? -> 아직 증명 못 함

 

 

Automata

• DFA(Deterministic Finite Automata)
  • 노드와 심볼이 결정되면 반드시 하나의 상태로만 이동
  • 즉, 입력이 결정되면 output은 항상 하나로 결정됨
    • ex) g(x,a) =y
    • x: input, a: action

• NFA(Non-deterministic Finite Automat)
  • 하나의 state에서 하나의 symbol이 주어졌을 때, 하나의 state만 결정되는 것이 아니라, 다른 state로도 갈 수 있다.
  • 노드, 심볼이 같아도 수행할 때마다 output이 달라질 수 있다.

 

 

Example: Subset-sum problem

• s={3, 8, 9, 100, ... }, k
• Optimization problem: 원소들의 합이 k를 넘지 않으면서, 가장 큰 subset은 무엇인가?
• Decision problem: 원소들의 합이 정확히 k인 subset이 존재하는가?
  • subset = {3, 9}이라는 certification이 주어졌을 때, 참인지 확인(verify) -> O(n)

 

 

 

☆NP Example☆

• 문제: weight가 k 이하인 MST 고르기
• Verification Algorithm:
  1. (n-1)개의 edges 집합(T)을 certificate로 사용
  2. spanning tree인지 테스트 -> 모든 정점 지나는지, input에 있는 정점만 지나는 지 확인 =>O(n)
  3. weight가 k 이하인지 테스트 => O(m)
• 분석: 테스트하는데 O(n+m) 시간이 걸림 -> 알고리즘이 polynomial time에 작동한다.
• 즉, 주어진 certificatation에 대해 다항 시간에 verification하기 때문에 Class NP에 포함되는 문제라고 볼 수 있다.

 

 

Class NP-Complete

• NP에 속하는 모든 문제가 Q로 reduction되면, problem Q를 NP-hard라고 한다.
• 모든 NP 문제를 다항시간 내에 NP-Complete 문제로 reduction할 수 있다.
• NP-Complete은 NP, NP-hard이다.
• NP-Complete는 다음의 조건을 만족하는 decision problems(C)의 집합이다.
  • C가 Class NP이어야 함
  • C가 NP-hard이어야 함
    • NP에 속하는 모든 문제를 다항 시간 안에 C로 변환할 수 있다.
    • 즉, reduction이 다항시긴에 이뤄짐
• NP-Complete문제들은 이때까지 알려진 다항시간 알고리즘이 없다
  • NP 클래스 중 어려운 문제인 NP-Complete가
  • NP-Complete가 다항시간에 풀린다면, NP 클래스의 모든 문제를 다항시간에 풀 수 있다고 볼 수 있다.
  • NP는 P에 속하기 때문에, 결과적으로 P=NP가 된다. 
• Q가 P보다 적어도 쉽지는 않다(hard)
• ex) 
  • problem P: 최솟값 찾기 문제
  • problem Q: sorting 문제
  • P를 Q로 풀 수 있다(reduction할 수 있다)

출처: https://zeddios.tistory.com/93

Polynomial Reductions

• P is reducible to Q: P$≤_p$Q
• P의 input을 Q의 input으로 다항시간으로 변환
• P의 output과 Q의 output이 같다는 것을 보여야 함.
• Reducibility relation은 transitive하다. -> A$≤_p$B, B$≤_p$C이면, A$≤_p$C이다

 

 

 

NP-Complete Problems

• NP-Complete 조건
  • Class NP: 다항시간에 verfification
  • NP-hard
• P: Hamitonian-Cycle 문제
  • 문제: Graph G가 주어졌을 때, 모든 정점을 한 번씩만 방문하는 simple cycle이 존재하는가?

 

• Q: Traveling Salesperson Problem(TSP) -> NP- Complete
  • 문제: complete, weighted graph G가 주어졌을 때, 모든 정점들을 한 번씩만 방문하고, 총 cost가 k가 넘지 않는 cycle이 존재하는가? 
  • Class NP인가?
    • 조건:
      • 다항시간에 verification해야 함 
    • certification (path)가 주어졌을 때, simple cycle이므로 n개의 edge를 거침 
    • 즉, O(n) time으로 verification할 수 있기 때문에 class NP라고 할 수 있다.
  • NP-hard인가? 
    • 조건:
      • 다항 시간에 문제의 input을 변환할 수 있는지 보여야 함 
      • 출력 결과가 같음을 보여야 함
    • Hamitonian-cycle 문제에서는 weight가 없는 일반 graph이기 때문에, 이를 complete-weighted graph로 변환해줘야 한다. (edge 추가, weight 추가, k 추가) -> O($n^2$)
      • 즉, 다항시간에 input 변환 가능
    • 다음과 같이, k가 0인 경우, weight가 0인 edge들로 이루어진 simple cycle이 존재하기 때문에, Hamitonian-cycle 문제에서도 simple cycle이 존재한다.
      • 반대도 마찬가지, TSP에서 simple cycle이 없으면, Hamitonian-cycle 문제에서도 simple cyle이 존재하지 않는다.

 

 

 

SAT

• Boolean formula
  • (a+b+￢d+e)(￢a+￢c)(￢b+c+d+e)
• 괄호들은 and 연산으로 연결된 것. -> (￢a+￢c)∧(￢b+c+d+e)
• a,b,c,d,e를 literal이라고 함
• iteral들이 or연산으로 되어 있는 절(￢b+c+d+e)을 clause라고 함
• 이렇게 or, and로 이루어진 형태를 Conjuctive Normal Form(CNF)라고 함
• SAT: literal에 0 또는 1을 할당해서, 이 연산의 결과 값이 true(1)인가?
• SAT은 Class NP인가?
  • 주어진 certification(literal에 값 넣은 것)을 수행해보면 됨 -> O(n) time(다항시간)으로 verification 가능
• SAT는 NP-hard인가?
  • 최초 NP-Complete문제인 CIRCUIT-SAT을 reduction하기 때문에, NP-hard라고 할 수 있다.
• SAT은 Class NP이면서 NP-hard이기 때문에 NP-Complete이라고 할 수 있다.

 

 

3SAT

• 모든 clause 안에 3개의 literal만 있는 경우
• 3SAT도 NP-Complete
• SAT를 reduction 함
• k-SAT에서 K가 3이상인 경우 NP-Complete이다.
  • k가 2인 경우 -> 2-SAT은 다항 시간 내에 풀 수 있다 (NP hard 영역이 아님)
• 모든 NP 문제는 SAT으로 Reduction할 수 있다.

 

 

Vertex Cover

• 문제: 모든 edges를 커버하는 k개 이내의 vertices(w)이 존재하는가?
  • 하나의 edge가 한 쪽 정점에만 연결되도 커버한걸로 간주
  • 회색 정점: 모든 edges를 커버하는 최소 정점

• VERTEX-COVER은 Class NP이다.
  • Non-deterministical하게 사이즈가 k인 subset W를 고르고, W 모든 edge를 커버하는지
  • certification으로 정점들의 집합이 주어졌을 때, 각 정점들의 incident edges를 확인해서 cover할 때마다 체크하면 됨.
• VERTEX-COVER은 NP-Complete이다.
  • 3SAT을 reduction한다.
    • 3SAT에서 특정 변수들에 값 할당하고, 결과 체크하는 것 -> 각 정점들이 모든 edge 커버하는지 체크
    • 로 변환 가능

 

 

Some thoughts about P and NP

• 믿음: P는 NP의 부분집합(proper subset)일 것 이다.
• NP complete의 의미: NP-Complete 문제는 NP 중에서 가장 어려운 것들일 것이다.
  • Why? NP-complete 문제를 다항시간에 풀 수 있으면, NP에 있는 모든 문제를 다항시간에 풀 수 있기 때문이다.