알고리즘 이론 34강. P와 NP

 

[Tractability(쉬운 취급)]

: 몇몇 문제는 다루기 어렵다(intractable)

: 값이 커질수록 합리적인 시간(reasonable time)안에 풀수 없다.

 

# 합리적인 시간(resonable time)

: polynomial time(다항 시간) 이 기준이다.

 

# polynomial time(다항 시간) : O(n^2), O(n^3), O(1), O(nlogn) 등

# 다항시간 안에 있지 않은 것 : O(2^n), O(n^n), O(n!)

 

 

[다항시간 알고리즘(Polynomial-Time Algorithms)]

: 다항 시간(합리적인 시간)안에 풀수 있는 문제.

: 모든 문제가 다항 시간안에 해결 되지 않는다.  ex) 튜링의 "Halting PRoblem" : 컴퓨터로 시간 많이 줘도 해결 불가능

: 최적화 및 결정(dicision)문제 대부분은 다항 시간 알고리즘을 보여주지 않는다.

 

 

[최적화/결정 문제(Optimizaion/Decision Problems)]

# 최적화 문제 : 문제 X의 최적화된 해결책은 무엇인가?

  ex) 0-1 knapsack / Frational kanpsack / mst 등

  : 최적화문제는 결정 문제로 전환되곤 한다.

 

# 결정 문제 : yes/no의 대답을 가지고 있는 문제

  ex) 그래프 G는 MST의 weigh <= W 를 가지고 있는가?

 

# 많은 문제들이 결정과 최적화 버전을 가지고 있다.

  ex) 여행하는 판매원 문제 => 최적화 : 최소 weight cycle 을 찾아라 / 결정 : cycle의 무게 <= k 인가>?

 

 

 

[클래스 P]

: 다항시간내에 해결되는 알고리즘을 가지고 있는 결정(decision) 문제의 클래스

= 어떤 상수 k에 대해 O(n^k) 시간에 풀수 있는 문제

: O(p(n)) - 이때 p(n)은 n 상의 다항시간

: 항상 올바른 답을 계산하는방법

: 다항시간내에 해결되지 않으면 비효율적

 

 

 

[클래스 NP]

: '비결정적인 다행시간' 상에 존재(stand)

: 주로 "추측" or "평행선화(parallelize)" 방식으로 계산

: 다항 시간에 "확인할 수 있는" 문제로 구성

= 해의 "후보"가 주어지면 문제 입력 크기에 대한 다항 시간에 그 후보가 올바른 해인지 확인할 수 있음 의미

: 이 방식의 문제점은 "속도(quickly)"

 

 

# P ⊆ NP(아직 증명 X)

# NP-complete(완비) 문제는 NP에서 가장 어려운 문제이다.

# 대부분의 전문적인 문제는 P or NP-complete 문제이다.

# NP-complete 문제 : P로 해결가능하지만 NP로 해결되지 않는 문제(아직도 미제문제)

 

 

[Reducion(환원)]

: 한 문제를 다른 문제보다 쉽다 or 어렵다 를 말할 수 있는 방법

 

# 문제 A가 B보다 쉽다 가정 

  : B를 해결하는데 사용가능한 알고리즘으로 A를 해결할 수 있을때 성립한다는 이론

 

 

[SAT 문제]

: 알려진 결정론적 시간 알고리즘(deterministic polynomial time algoritm)은 존재하지 않는다.

: 그래도 다형 시간 안에 증명하기 쉽다.

: NP-complete 문제 예시 중 첫번째 문제

 

 

[P와 NP]

- P : 다형 시간안에 풀 수 있는 문제

- NP : 다형 시간안에 입증(verified) 될수 있는 문제

 

# P 문제들 : 솔루션에 대한 효율적인 발견(discovery)

# NP 문제들 : 솔루션에 대한 효율적인 증명(verification)