Computational Complexity(계산 복잡도 이론)

https://com24everyday.tistory.com/198

P, NP, NP-Hard, NP-Complete

 

 

Traveling Salesperson Problem 

exponential 보다 나은 시간 복잡도 없음

NP-Complete

 

 

 

Intractability (아주 다루기 힘듦)

"difficult to treat or work"

- 효율적 알고리즘 없음

- 증명 안됨 

- 자연에 있는 많은 최적화 문제

 

 

 

 

Tractable (다루기 쉬움)

만약 문제를 풀 수 있는 polynomial-bound algorithm 이 있으면 다루기 쉽다.

 

nlogn 은 polynomial 아님

nlogn< n^2  bound by a polynomial

 

 

 

Intractable 

not bounded by a polynomial 

c^n, n^log n , n!

 

 

 

Theorem 9.1

만약 decision problem B 가 P 그리고 A 는 B에 속한다면 decision problem A는 P 이다.