논문을 보다보면 NP-hard라는 용어가 나온다.
무슨 뜻인지 궁금해서 인터네에 쳐봤는데, 꽤 어려운 말들이 나왔다.
여러번 포기했었지만, 제대로 알고 넘어가고자 관련 내용들을 블로그에 정리해보기로 했다.
일단 NP-hard를 이해하려면, P와 NP부터 알아야하기에 이번에는 P, NP에 대해 알아보겠다.
P? NP? 무엇에 관한 용어인가?
이론적으로는, 복잡도 종류와 관련된 용어이다.
복잡도 종류란, 계산 복잡도 이론에서 계산 복잡도에 따라 문제를 분류한 것인데, 복잡도 종류의 정의는 일반적으로 다음과 같다.
추상기계 M이 O(f(n)) 만큼의 자원 R을 이용하여 풀 수 있는 문제의 종류 (n은 입력의 길이)
뭔가 말이 어렵다…
이런 저런 자료들을 찾아서 내가 이해한 바로는, 문제가 쉽냐 어렵나에 따라 구분한 것이다.
문제가 쉽다는 것은 짧은 시간 내에 문제를 풀 수 있다는 것이고,
그렇지 않은 문제는 어려운 문제다.
그래서 P는 뭔가?
이론적으로, P는 다음과 같이 정의된다.
다항식 시간(polynomial-time)의 알고리즘으로 풀리는 결정 문제(decision problem)의 집합
흠,,다항식 시간이 뭐고 결정 문제는 뭔가..? 하나하나 살펴보면,
먼저, 결정문제는 Yes/No로 대답할 수 있는 문제를 말한다.
그리고 다항식 시간이란 입력의 크기 n의 다항식으로 표시되는 시간이다.
예를 들어, \(3n^k + 5n^{k-1} + ...\)은 다항식 시간이며 \(2^n\), \(n!\)등은 다항시간이 아니다.
즉, 다항시간 알고리즘이라 하면, Big O표기법으로 O(\(n^k\))를 만족하는 알고리즘을 말한다.
종합적으로, P를 간단히 말하자면, 답을 찾는 데 걸리는 시간이 짧은 문제다.
즉, 쉬운 문제다. 어쨋든 풀 수는 있는 문제이기 때문이다.
그렇다면 NP는 뭔가?
이론적으로 NP는 다음과 같이 정의된다.
비결정적 다항식시간(polynomial-time nondeterministic) 알고리즘으로 풀리는 결정 문제(decision problem)의 집합
…비결정적은 뭐지?
비결정적을 이야기하기 전에, 결정적(deterministic)하다는 것에 대해 먼저 알아보자.
결정적이라는 것은 계산 단계에서 하나의 가능성만을 고려하면 되는 것이다.
하지만 비결정적이라는 것은 그렇지 않다. 매 단계 여러가지 가능성이 존재한다.
그래서 비결정적 다항시간 알고리즘은 하나의 input에 대해서 다른 output이 나올 수가 있다.
…그래서 저게 무슨 뜻이냐..?
이렇게 많은 경우의 수를 가진 알고리즘으로 어찌저찌 답이 나오는 결정문제라면 NP인 것이다. 간단히 말하자면 운이 좋으면 풀 수 있는 문제다.
그래서 NP를 이런 식으로 설명하기도 한다.
어떤 문제에 어떤 답을 넣었을 때 그게 진짜 답임을 보일 수 있으면 그 문제는 NP에 속한다고..!
어떤 방정식이 있다고 하자.
그리고 그 방정식에 대한 어떤 해가 주어졌다고 할때, 그 해가 맞는 지 알아보기 위해서 우리는 그저 방정식에 그 해를 대입해보고 등식이 성립하는 지 확인한다.
그리고 이는 다항시간 내에 이루어진다.
그렇다면 그 문제는 NP인 것이다.
아주 간단하게 NP를 설명하자면, 풀기는 어려울 수 있지만, 답이 맞는지는 확인하기 쉬운 문제다!
P와 NP의 관계!
P문제가 주어졌을 때, 그 문제의 답이 YES라면, 그 답을 힌트삼아 그 문제의 답이 YES라는 것을 쉽게 확인할 수 있다.
그러니 P문제는 NP이기도 하다. 즉, P \(\subset\) NP 인 것이다.
그렇다면 NP는 P일까?
이는 아직 증명되지 않은 7개의 ‘밀레니엄 문제’ 중 하다다.
P=NP가 의미하는 바는 상당히 크다. 어떤 문제가 주어졌을 때 문제의 답을 쉽게 검산할 수 있다면 그 문제를 푸는 것도 쉽다는 이야기이기 때문이다.
위키백과를 비롯해 많은 블로그들을 참고하여 정리해봤습니다.
어렴풋이 이해하고 정리한 내용이라 맞지 않은 내용이 있을 수 있으니 피드백 주시면 정말 감사하겠습니다.
다음에는 정말 알아보고자했던 NP-hard와 NP-complete 등에 대해 알아보겠습니다.