# 3단계 문제 난이도

P: 폴리노미얼 타임으로 정답을 구할 수 있는 문제


NP: 임의의 값 1가지에 대해 정답인지 아닌지만 폴리노미얼로 계산할 수 있는 문제. NP를 풀려면 서치나 샘플링등의 계산적인 접근을 해야한다.


NP-Hard: NP보다 조금이라도 무조건 더 어려운 문제. 얘는 계산적인 방법으로도 풀기힘든 문제이다.


# NP-complete의 특수한 성질

어떤 NP가 다른 NP로 컨버팅이 될때, 그 컨버팅 타겟문제를 지칭하는 말이다. 이녀석들 덕분에 P=NP 라는게 증명되면 왠만한문제가 다풀리는것이다.

https://www.quora.com/What-does-NP-hard-mean





P : 어떤 문제의 해답을 빠른 시간(=다항 함수)안에 찾을 수 있는 문제.

다항 함수 : 한 변수의 곱셈과 덧셈으로만 이루어진 식. ex) 3+2x^2+5x^3(2^x승 같은 것은 포함되지 않는다.)


NP : 어떤 문제에 대해 내가 제시한 답이 정답인지 아닌지만 빠른 시간안에 O,X로 판단 할 수 있는 문제.
(따라서 정답을 찾는 데 매우 오랜 시간이 걸린다. 어떤 문제를 빠른 시간안에 풀 수 있는 알고리즘이 존재한다고 증명되는 순간 그 문제는 P에 속한다.)

이때 만약 어떤 문제가 P라면, 그 문제는 NP에 속한다(집합). 왜냐하면 P라면 빠른 시간안에 정답을 찾을 수 있기 때문에, NP에서 정의한 주어진 값이 정답인지 아닌지 알아내는 것은 너무나 쉽기 때문이다.


NP-Hard : 모든 NP 문제들을 빠른 시간 안에 이 NP 문제로 Reduction 이 가능할 때.
(Reduction은 문맥상의 의미만 간단히 말하면, A라는 문제를 B문제로 바꾸어서 풀 수 있다는 것이다. 참고로 이때 문제를 바꾸는데에는 다항함수 시간이 걸린다.)


NP-Complete : NP이면서 NP-Hard인 문제. 즉 모든 NP 문제들이 'NP문제'로 Reduction이 가능할 때.

(어떤 NP 문제가 다항함수 시간안에 NP-Complete으로 Reduction이 가능한 경우, 그 문제도 역시 NP-Complete임이 증명되어있다. 그래서 1개의 NP-Complete이 발견된 이후 많은 문제들이 그 문제를 통해 Reduction 되어 NP-Complete임을 증명했다.)



또한 "P이면 NP이다" 는 앞서 본 것 처럼 증명이 되었지만, "NP이면 P이다"라는 명제는 참,거짓이 아직 증명되지 않았다. 아래 그림은 P=NP임이 증명 되었을 때와 P≠NP임이 증명되었을 때의 현상을 잘 나타낸다.


NP=P라면 당연히 NP-Complete 또한 P이므로, 이 말은 수 많은 어려운 문제들을 다항 함수시간안에 풀 수 있다는 것이다. 

마찬가지로 또한 NP-Complete 문제 중 하나를 다항함수 시간안에 풀어낸다는 것은 NP-Complete = P 라는 것이고, 이 역시 Reduction 을 통해 NP=P라는 것과 완전히 동일하다.

현재까지 NP-Complete인 문제 중 다항함수 시간안에 해를 구해내는 알고리즘은 단 하나도 발견되지 않았다. 만약 하나라도 NP-Complete 문제를 다항함수 시간안에 풀 수만 있다면, 모든 NP-Complete을 그 문제로 Reduction 하여 다항함수 시간안에 풀 수 있는 P문제가 되어버린다.



- 시간 복잡도와 Entropy

어떤 문제를 풀기위한 알고리즘의 최소시간 복잡도를 알 수 있을까? 
알 수 있는 문제가 바로 P 이고, 알 수 없는 문제가 바로 NP이다.

(단, 여기서 말하는 시간복잡도는 Worst case에대한 시간복잡도만을 의미한다.)

(시간복잡도에대해 배울때, 사실은 Best case, Average case, Worst case로 시간복잡도를 나타내는 것이 모두 가능하다. 다만 우리는 이 때 Worst case에서의 시간복잡도에 관심이 있는 것이라 일반적으로 시간복잡도라 함은 Worst case를 말하며 이것을 O( f(n) ) 꼴로 나타낸다.)

(http://stunstun.tistory.com/83 참조)


그러면 어떤 알고리즘의 시간복잡도와 entropy는 관련이 있을까?

일단 시간복잡도가 entropy는 아니다.
같은 데이터(정보)를 다룰 때, 다른 알고리즘을 쓰면 entropy는 변하지 않지만 시간복잡도는 알고리즘에 따라 변한다.

ex) 1개의 bit를 반전시키는 알고리즘의 시간 복잡도는 1이다.
ex) 1개의 bit를 3번 반전시키는 알고리즘의 시간 복잡도는 3이다.


즉, entropy와 시간복잡도는 완전히 적용 대상이 다른 개념이라 서로 직접적인 연관성은 없다.
entropy는 데이터가 가진 정보량의 평균값이고, 시간복잡도는 어떤 알고리즘이 수행되는데 걸리는 시간이다.

다만, 어떤 알고리즘에서는 시간복잡도와 entropy가 같을 수 있지만, 이것은 그냥 우연한 하나의 예일 뿐이다.
(bit를 다루는 이진트리의 경우에서 찾을 수 있음.)


http://yoonho.info/19

http://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84

http://blog.naver.com/gateway21c/167923111


by 곽동현 이스텔리앙 2014. 7. 22. 19:34