[알고리즘] NP-completeness(2)

[Solvable problems]

 

Solvable problems는 세 가지 유형으로 구분할 수 있다.

 

1) Provably intractable (infeasible) problems : efficient한 알고리즘이 존재하지 않는 문제들(polynomial time 알고리즘에 존재하지 않는다고 증명된 문제들)

2) Probably intractable problems : polynomial time 알고리즘에 존재하지 않는다고 추측할 수 있는 문제들 => NP

3) Tractable problems (feasible problems) : polynomial time 안에 해결할 수 있는 문제들 => P

 

 

-

1) Provably intractable (infeasible) problems :

polynomial time 알고리즘에 존재할 수 없다고 증명된 문제들을 말한다.

 

ex) Generalized chess

일반 체스 -> size N x N

-> best case runtime이 exponential이라고 증명됐다! (lower bound)

 

2) Probably intractable problems :

NP class로서 어려운 문제인 것 같다고 추측할 수 있는 문제들을 말한다.

 

ex) Any NP problem, such as Traveling Salesman

 

3) Tractable problems (feasible problems) :

polynomial time solution이 존재한다고 입증된 문제들을 말한다.

-> sorting problem은 polynomial time 알고리즘이 존재하는 문제임을 보여준다.

 

ex) Any P problem, such as Sorting

* P problem : polynomial time 안에 존재하는 문제들

 

 

[Polynomial time algorithms]

 

polynomial time 알고리즘이란?

=> polynomial time안에 결정적인(범용적인) 튜링 머신에 의해 수행되는 알고리즘을 말한다. (input size에 비례적인)

 

*deterministic TM은 한 번에 하나의 point를 수행한다. 즉, only one possible action을 수행

-> P class of problems는 polynomial time 안에 deterministic TM에 의해 해결될 수 있는 모든 problem들의 집합을 말한다.

-> O(n^k) for some constant k, where n is the size of the input to the problem

 

[Determinism & Nondeterminism]

 

> FSA

Finite State Automaton(FSA)는 deterministic 혹은 nondeterministic으로 구분 가능

 

- deterministic FSA : 정확히 하나의 arc만 존재 

- nondeterministic FSA : 한 개 이상의 arcs 존재(모든 상태에서 나가는 아크가 2개 이상이 아닐 수도 있으니까)

 

*각각의 symbol에 대해서 transition이 1개여야 deterministic이라고 할 수 있다.

*만약 어떤 TM이 deterministic TM이라면, 그 TM은 nondeterministic TM이라고도 말할 수 있다! (포함됨)

(왜냐하면, nondeterministic 특성이 deterministic 특성을 포함하고 있으니까)

 

> TM

Turing Machine에서도 똑같이 적용된다.

nondeterministic TM은 두개 이상의 action을 가진다.

 

*이 때 어떻게 TM이 path를 follow할 수 있을까?

- 여러 머신들로 split하여 각 가능한 path들을 follow하는 방법

- 그냥 right path를 guess하여 찍는 방법

 

[NP Class of Problems]

 

*Nondeterministic은 TM이 같은 input을 넣었을 때 다른 output들을 가지는 것을 allow한다.

-> problem이 NP임을 보이기 위해서, 우리는 주어진 solution이 타당한지 check하기 위해 polynomial time 알고리즘을 찾을 필요가 있다!

 

*NP class of problems은 polynomial time안에 nondeterministic TM에 의해 해결될 수 있는 모든 문제들의 집합이다.

*NP stands for "nondeterministic polynomial"

*It doesn't stand for "non-polynomial"!!!!!!!!

 

Class NP는 polynomial time안에 "verifiable"하는 problem들로 구성되어 있다.

만약 우리가 solution의 하나의 "certificate(path가 갖고있는 정보, 후보군들 중 하나)"가 있다면, 우리는 certificate가 polynomial time안에 correct하다고 verify할 수 있다.

*certificate(path) : solution이 될 수 있는 후보들 중 하나

 

> Decision problem : 결정해야 하는 문제인지~ yes or no

 

> Definition : 다음을 만족할 때 하나의 problem은 NP에 속한다. (decision problem일 때)

1) certificates whose length are polynomial in the size of the problem instance, and (certificate가 있나요?)

2) an algorithm that verifies certificates in time polynomial in the size of thhe problem instance. (certificate를 verify할 수 있는 알고리즘이 있나요? - > polynomial time안에 풀리는지)

 

> 예시

Problem : LongPath(G, k)라는 최소 k 길이의 path가 있는지 물어보는 problem이 있다고 하자. 

Proposition : The problem LongPath(G, k)는 NP에 속한다.

Proof :

1) LongPath(G, k)는 decision problem이고 NP의 정의를 충족한다.

2) certificate는 적어도 k길이의 path를 이루는 vertice들의 list이다.

3) certificate를 verifying하는 알고리즘이 있다.

G : 주어진 graph

k : length

m : certificate에 들어있는 node들의 개수

 

> P에 있는 모든 problem들은 NP에 자동으로 속한다. -> deterministic 알고리즘이 empty 추측 단계를 갖는 nondeterministic 알고리즘이라고 여길 수 있기 때문에!

> 그래서 우리는 P가 NP의 subset이란 것을 알 수 있다.

P : 모든 problem들의 집합(deterministic 문제에 의해 polynomial time안에 solve되는 집합)

> 하지만, NP에는 있지만 P에는 없는 문제가 있는지는 알 수 없다!

> P = NP가 성립하는지의 문제는 컴퓨터 과학 분야에서 아직 해결되지 않았다.

 

[NP-Complete Problems]

 

> NP-complete problem들은 NP의 subset이다.

*NP-complete problem : NP에 속한 문제들 중 가장 어려운 문제 (hardest problems in the class NP)

 

ex) 곱셉문제를 NP, 덧셈문제를 NP-complete라고 예시로 들 수 있다.

 

=> NP의 문제들은 polynomial하게 reduce(환원)될 수 있다.

=> 즉, NP의 모든 문제는 polynomial time 안에 실행되는 알고리즘에 의해 NP-complete problem으로 줄일 수 있다. (축소 가능)

 

=> 모든 NP-Complete problem들은 polynomial time안에 다른 NP-complete problem으로 reducible가능하다!

*NP-complete problem들은 자기들끼리도 reducing이 가능하다.

ex) X를 Y로 polynomial time안에 reducing하여 solve한다고 해석

 

> "reducible"의 의미

decision problem Q는 문제 Q의 각 인스턴스를 문제 Q'의 인스턴스로 변화시키는 polynomial time 알고리즘이 develop될 수 있다면, decision problem Q'로 reduce(환원)할 수 있다!

 

=> Q라는 문제가 Q'라는 문제로 polynomial time 안에 reduce된다!

*Q'가 더 어려운 문제 (NP-complete problem)

 

> Definition

problem Q'는 NP-Complete이다. 

if :

1) Q'가 class NP의 element일 때

2) NP에 있는 모든 problem Q에 대해서, Q<=Q'를 만족할 때

 

=> 즉, NP의 모든 Q는 NP의 Q'보다 더 어렵지 않은 polynomial factor 이하이다.

=> 가능하다면 모든 NP문제들을 NP-Complete로 풀 수 있다.