[Algorithms] NP 이론(NP theory)

알고리즘 수업을 들을때도 이 부분은 안드로메다였는데,
뭔가 알겠다 싶었는데 다시 보니까 더 헷갈린다. 그래도 안볼수는 없으니 이해하며 정리해보자. 

일단 Decision problem의 정의에 대해서 알아야 한다.
Decision Problem은 어떠한 인스턴스에 대해서 "yes" or "no"로 답할 수 있는 문제를 말한다. 
쉬운 예를 들자면, 스무고개를 하면 질문을 할때 예 또는 아니오로만 답할 수 있는 질문을 해야한다.
그러한 문제들을 decision problem이라고 보면 되겠다.

이어서 집합 P와 NP의 정의는 다음과 같다.

P : 다항식 시간(polynomial-time)의 알고리즘으로 풀리는 decision problem의 집합
NP : 비결정적 다항식시간(polynomial-time nondeterministic) 알고리즘으로 풀리는 decision problem의 집합

 
이 정의부터 왠지 안드로메다 느낌이 나기 시작한다...ㅜㅜ 그래도 열심히 이해해 보자

컴싸에서 가끔씩 deterministic, nondeterministic이라는 용어가 나온다.
예전에는 각각 무엇을 뜻하는지는 알았으나 설명할 수는 없을정도로 이해하고 있었는데, 최근에 확실히 이해했다.
deterministic은 어떠한 인스턴스에 대해 항상 같은 결과가 나오는 것이고
nondeterministic은 무엇인가 불확실한 것이 있어 시행하는 방식에 있어 다른 결과가 나올 수 있는 것이다.
만약 어떤 문제를 deterministic하게 풀었다고 하면 FM으로 푼 것이고, nondeterministic이면 야매로 풀었다고 할까?

본론으로 돌아가서,
NP는 어떠한 문제를 추측하고 그것을 검증(verify)하는 방식으로 문제를 푸는데 그것이 polynomial time에 풀어지는 결정문제의 집합인 것이다.
예를들어, A와 B가 가위바위보를 하는데, A는 이기는가? 라는 문제가 있다고 가정해보자.
이때 A-가위 B-보 라는 인스턴스를 추측(guess)하고 실제로 가위바위보 룰을 정해놓고 검증했을때 참이 되면 비결정적인 다항식 시간으로 문제를 푼 것이기 때문에 저 문제는 NP가 된다.

여기서 P와 NP와의 관계가 중요해 진다.
과연, P는 NP의 proper subset인가? 혹은, P-NP=공집합인가?
직관적인 느낌으로는 당연히 P는 proper subset이라고 생각된다.
하지만, NP의 문제가 다항식 시간내에 풀리는지 아니면 풀리지 않는지 증명되지 않았으므로 그것은 알 수 없다.
확실한 것은 P⊆NP 뿐이다.


이어서 나오는 NP-complete의 정의를 위해,
Polynomial time many-to-one reducibility의 정의가 필요하다.
이것은 기호로는 ∝로 나타내며 A의 모든 문제의 인스턴스가 B의 인스턴스로 polynomial time에 변환 가능하다면 A∝B라고 한다.

NP-complete의 정의는 다음과 같다.

어떠한 problem B에 대해서,
1. B는 NP이고,
2. NP의 모든 문제 A에 대해서  A∝B이다.
그러면 B는 NP-complete이다. 

 
또한 다른식으로 표현하면

어떠한 problem B에 대해서,
1. B는 NP이고,
2. NP-complete의 어떤 문제 A에 대해서  A∝B이다.
그러면 B는 NP-complete이다. 

 
빨간 박스의 정의가 보다 포멀한 정의다.
정의에 의하면 초록 박스의 내용은 쉽게 증명될 수 있다.

위의 성질에 따라서, 만약 NP-compete 문제 중에서 하나라도 P라는 것이 증명되면,
NP-complete 문제는 전부 P가 되게 된다.

일반적으로 말하는 NP(혹은 NP-complete) 문제는, 아직 다항식으로 풀게되는 알고리즘이 나오지 않은 것으로써 
알고리즘계의 '난제'로 꼽힌다.


마지막으로 NP-hard에 대해서 알아보자.
일단 부가적으로 Polynomial-time Turing reducibility 개념이 나온다.
이는 어떠한 문제 A가 hypothetical polynomial-time 알고리즘 B에 의해 polynomial time으로 풀린다면
문제A는 문제 B에 대해 polynomial time Turing reducible하다고 하며 A∝tB로 표기된다.
(도대체 뭔뜻이냐!! ㅜㅜ)
B는 반드시 존재할 필요는 없다고 한다. 또한 A와 B는 결정문제일 필요도 없다.

이에 의해 NP-hard의 정리는 다음과 같다.

어떤 NP-complete 문제 A에 대해서, A∝tB 이면 문제 B는 NP-hard이다.

 B는 NP일 필요도 없고 결정 문제일 필요도 없다.
정의를 곰곰이 생각해 보면 다항식 시간이라고 가정한 알고리즘에 대해서 튜링 리듀서블 했지만,
만약 정말로 다항식이 된다면 P=NP가 됨을 알 수 있다.
NP-complete는 P가 될 것이고 그렇게 되면 NP-complete는 NP의 부분집합이기에 P=NP가 될 것이다. 
이는 기존의 NP-complete 문제가 yes or no로만 답하게 되는 결정문제이기 때문에 그것을 일반적인 최적화 알고리즘에 대응시키기 위한 정의이다.

정말 Turing은 천잰가보다.