P-NP Problems

1. Class P

 1) 문제 복잡도란?

: 문제를 해결하는 가장 최적의 알고리즘의 복잡도를 의미한다. 이는 문제를 해결하기 위한 최소한의 연산수와 같다.

EX) unsorted array에서 최댓값 찾기: Ω(n), unsorted array 정렬하기: Ω(nlogn)

 

2) Class P의 정의

이는 Polynomial-time안에 수행되는 알고리즘들의 집합으로, T(n)=O(n^k) 안에 수행이 되어야 한다.

즉, 이는 n,n^2,nlogn...등의 모든 알고리즘이 포함된다. 지금까지 배운 보편적인 알고리즘들은 모두 Class P에 들어가 있다.

 

 

2. Class NP

1) Premise

-> 어떤 문제는 아직 polynomial time안에 풀수 있는지/불가능한지조차 알려지지 않았다.

EX) 0/1 knapsack problem, traveling salesperson problem

: 다시 강조한다. 풀 수 없는게 아니라, polynomial-time algorithm이 아직 발견되지 않은 것이다.

 

2) Optimization Problems VS Decision Problems

 - 최적해 문제는, 가장 좋은 가치를 갖는 solution을 찾는것으로, shortest-path 문제와 MST등의 예시가 있다.

 - 하지만 Decision problem은 단순히 yes/no의 문제로, 해당 solution이 존재하는지? 하지 않는지만을 대답한다.

EX) 최적해 문제는 목적지 까지 10분내에 가려면 어떻게 가야하는가? 를 묻는것이고, Decision problem은 목적지까지 10분내에 가는 path가 존재하는가? 만 묻는다. 당연히 최적해 문제가 더 어렵고, 이 문제를 풀면 decision problem도 풀 수 있다.

 

3) Class NP의 정의

-> 만약 Problem에 대한 non-deterministic polynomial time algorithm이 존재하면 이를 class NP라고 한다.

=이는 problem에 대한 solution이 polynomial time안에 verifiable하냐? 와 동일한 뜻이다.

우선 verification은 문제를 검증하는 과정인데, 어떤 문제에 대한 solution(ceritificate)이 맞는지/틀린지 검증하는 과정이 polynomial time안에 끝나면 이 문제는 class NP에 속한다고 할 수 있다.

 

예를 들어 설명해보자면, 만약 질문에 어떤 path를 구할때, 이 path의 가중치 합이 17이하인 path가 존재하면 yes, 존재하지 않으면 no라고 대답하는 verification 과정이 있다고 가정하자. weigth의 합이 15 이하인 path가 주어졌을때, 이를 검증하는 과정이 polynomial time안에 수행되면 이 문제는 class NP인 것이다.

그렇지만, 17짜리인 path가 주어졌을때 저 질문에 대해 NO라고 할수 있느냐 하면, 그것도 아니다. 이 path하나로 아예 존재하지 않는지는 단정지을 수 없는 일이므로 대답을 하지 못하는 것이다.

 

EX2) 만약 어떤 사람이 Weighted Graph를 하나 주고, 여기서 weight가 최대 k인 MST가 존재하는지 물어본다면

우선 spanning tree의 조건을 만족하는지 확인하기 위해 MST가 graph의 모든 vertex를 포함하는지. n-1개의 edge로 구성되어있는지, cycle은 없는지 확인할 것이다 -> 이를 판별하는데에는 다항 시간이 걸린다. 

또, edge들의 weight의 합을 구한다 -> 이를 판별하는 데에도 역시 다항 시간이 걸린다.

-> 즉 verification시간이 O(n+m), polynomial time이 걸림 -> 이는 non-deterministic polynomial time algorithm이다.

4) Trivia

- 문제를 polynomial time안에 풀 수 있으면, 당연히 verification 과정도 polynomial time안에 수행이 가능하다.

따라서 class P는 모두 Class NP에 속한다. 그렇지만 P=NP 인가? 이건 아직 증명을 아무도 하지 못했다.

- verification algorithm은 solution algorithm과는 다르다!!

 

 

3. Class NP-Complete & Class NP hard

1) NP-hard

: NP 안의 모든 문제가 Q보다 쉬우면 이 문제 Q를 NP-hard문제라고 한다. 이를 정확한 정의로 다시 정의해보자면,

NP class안에 있는 모든 문제가 Q로 reducible하면 이를 NP-hard라고 한다.

"Reducible" 개념을 이해가 위해선 Transformation function에 대해 이해해야 한다.

 

1) 만약 P에 대한 input 을 일련의 transformation과정을 거쳐 Q에 대한 input으로 만들었다고 가정해보자. 이 과정은 Polynomial time안에 가능할때, Polynomial reduction이라고 한다.

2) 이 function을 거친 T(X)를 Q에 대한 input으로 그대로 넣어보자. Q의 decision algorithm을 거쳐 yes/no중 어떤 대답이 나오는지 보자. 

3) 그리고 이 답을 X를 P에 대한 algorithm에 넣었을때에 대한 대답으로 사용해버리자. 만약 Q의 답을 통해 P를 풀게 되었을때, 이게 맞으면 P는 Q로 reducible한 것이다. 즉 Q에 대해 Yes라서 P에 대해서도 Yes라고 했을때, 이가 맞으면 P는 Q로 reducible한것이다.

 

Q) 이를 상식적으로 생각했을때, 그렇다면 P가 더 어려운 문제일까, Q가 더 어려운 문제일까?

A) 당연히 Q를 풀면 P도 풀 수 있는 것이므로 Q가 더 어려운 것임. P가 Q에 대해 종속적이라고 생각하자.

 

- 여기서 용어를 잘 봐야 한다.

1) P is reducible to Q이면, Q가 P 보다 어려운것.

2) Q is reducible from P이면, Q가 P보다 어려운것. 위와 아래는 같은 표현이다.

 

2) NP-COMPLETE

- 이 문제가 NP안에 있음과 동시에, NP-HARD이면 이는 NP-COMPLETE이다. 

ex) 만약 NP 반 안의 그 어떤 학생보다 강한 사람이 있을때, 이 사람이 전학을 오면 그 반의 학생 신분이 되므로 이 사람은 NP-COMPLETE이 되는 것이다.

: 즉 NP내에서 가장 어려운 문제라고 할 수 있겠다. 아래는 알려진 NP-COMPLETE 문제이다.

 

EX1) SET-COVER :

• 전체 집합 U와, 그 부분 집합 Si들을 원소로 갖는 집합 F가 있다고 하자.
• F의 원소인 Si들을 합집합하여 전체 집합 U와 같아지는 집합 Si들의 최소 개수를 찾는 문제이다.

 ->따라서 SET이 전체를 커버할 수 있냐? 와 같은 말, 이는 VERTEX-COVER로부터 reduce된 NP-Complete 문제이다.

 

EX2) SUBSET-SUM:

• 정수의 set이 주어졌고, K가 주어졌을때, 이 set의 부분집합의 원소의 합이 K인 부분집합이 존재하는가?                    

-> 이 문제 역시 VERTEX-Cover 로부터 reduce된 NP-COMPLETE 문제이다.

 

EX3) 0/1 knapsack

: 만약 weight, benefit이 명시된 item의 집합이 존재할때, weight가 최대 W이상이며 이익은 최소 K인 subset을 구하여라

-> 이 문제는 SUBSET-SUM으로부터 reduce되었다.

 

EX4) Hamiltonian-Cycle

: Graph G가 주어졌을때, 모든 vertex들을 모두 한번만 방문할 수 있는 cycle이 존재하는가?

-> 이 문제는 VERTEX-COVER로부터 reduce되었다.

 

EX5) Traveling Salesperson Tour

:만약 complete weighted graph G가 주어졌을때, 모든 vertex를 한번씩 통과하고(해밀턴 사이클), 이 edge들의 가중치의 합이 K이하인 cycle이 존재하는가?

-> 이 문제는 Hamiltonian-Cycle로부터 reduce되었다.

 

따라서 어려움의 난도로 따지면

VERTEX-COVER<SET-COVER, VERTEX-COVER<SUBSET-SUM<0/1 KNAPSACK , VERTEX-COVER<HAMILTONIAN CYCLE<TST이다. Reducibility relation은 transitive하므로 상위 문제를 풀면 하위 문제를 모두 해결할 수 있다고 볼 수 있다.

 

 

3) NP-COMPLETE임을 어떻게 증명하는가?

만약 NP CLASS에서 어떤 학생 4명이 가장 강하다고 가정했을때, 이 4명은 NP클래스 내의 어떤 문제들 보다 강하므로 NP-HARD이면서, NP CLASS 내에 있으니 NP-COMPLETE이다.

이때, 어떤 전학생이 와서 자기도 NP-COMPLETE가 되고 싶다고 했을때, 가장 쉬운 방법은 가장 강한 네명과 싸워보는 것.

만약 이 네 명하고만 이기면 NP CLASS에서 가장 어려운 문제를 이긴 것이니, 이 문제 역시 NP-COMPLETE가 되는 것이다. (나중에도 이긴다는 보장은 없으니 다섯 명 다 NP-COMPLETE으로 남아있다고 하자 ㅎㅎ)

 

쉬운 방식으로 예를 들었지만, 따라서 이 문제가 NP-COMPLETE임은 어떻게 증명하는가?

1) 이 문제가 NP임을 증명한다.

: 어떤 certificate가 다항 시간 내에 verify되면, 이 문제는 NP이다.

 

2) 이 문제가 NP-HARD임을 증명한다.

: 즉, 새로운 문제 Q가 발생했을때, 이 문제를 통해 기존 NP클래스 안의 가장 어려운 문제였던 NP-COMPLETE문제가 해결되게 되면, 이 NP안의 모든 문제가 Q로 reducible해져(즉, NP안에서 가장 어려운 문제가 Q를 통해 풀린 것임) Q가 NP-HARD임을 증명 할수 있는 것이다. 

 

즉 Q는 NP이면서 NP-HARD이므로,(전학생이 기존의 강한 사람들과 겨뤄서 이김) Q는 NP-COMPLETE이 되는 것이다.

 

+) 만약 알려진 어떤 NP-COMPLETE 문제라도 다항시간 안에 풀리는 알고리즘이 발견되면 모든 NP-COMPLETE 알고리즘은 서로 REDUCE되기 때문에 P=NP임을 증명할 수 있다. 하지만 이건 100만달러가 걸린 40년동안의 난제라는 것ㅎㅎ

 

 

4) SAT, 3SAT, VERTEX COVER

 1) SAT 문제는 최초의 NP-COMPLETE문제이다.

: 충족 가능성 문제(satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다.

 -> CIRCUIT-SAT로부터 reduce되었다. : CIRCUIT-SAT reduces to SAT

 

 2) 3SAT는 SAT의 논리식 개수를 3개로 제한했다. 

-> SAT로부터 reduce되었다. : SAT reduce to 3SAT

 

즉, 3SAT를 풀면 SAT를 풀고, SAT를 풀면 CIRCUIT-SAT을 풀 수 있는 것이다.

 

3) VERTEX-COVER

: 정점 커버 문제는 주어진 그래프 G에서 각 edge의 양 끝 vertex중 적어도 하나의 끝 점을 포함하는 점들의 집합 중에 최소 크기의 집합을 찾는 문제이다. vertex-cover를 살펴보면 그래프의 모든 선분이 정점 커버에 속한 점에 인접해있다. 그래프의 모든 edge들은 집합 내 점들 중 하나라도 연결되어 있어야 한다.

-> 이 문제는 subset의 size k와, subset W에 의해 cover된 edge를 검사하면 되므로 vertex-cover의 verification은 Polynomial time에 끝난다.  따라서 이 문제는 NP클래스에 속하며, 3SAT으로부터 reduction되는 NP-COMPLETE문제이다.