개인공부 조각들

P-NP

컴퓨터로 푸는 문제라는 것은 무엇일까?

문제의 엄밀한 정의는 “입력 집합과 해답 집합 사이의 어떤 관계”라고 할 수 있겠다.

그런데 수많은 형태를 지닌 문제들을 모두 고려하는 것은 쉬운일이 아니기에 입력이 참 또는 거짓인지만 다지는 결정 문제에 대해서만 생각해보려고 한다.

\[S:=\lbrace true, false \rbrace\]

사실, 결정 문제만으로도 임의의 문제를 표현하는데는 큰 문제가 없다고 한다; 증명을 포함한 추가 내용들은 더 공부해보아야 할 것 같다.

알고리즘이 입력의 다항시간 안에 해결될 때, 이를 효율적인 알고리즘이라고 부른다.

다항시간이란 시간복잡도가 주어진 입력의 크기 $n$에 대한 적절한 다항식으로 표현될 수 있다는 것이다. $2^n$과 같은 시간복잡도는 지수 시간이며, 효율적인 알고리즘이 아니다.

위 블로그의 예시가 정말 좋은 것 같다.

여러가지 경우의 수를 동시에 계산할 수 있는, 여러가지 풀이 가능성을 고려할 수 있는 비결정론적 알고리즘. 마치 휴리스틱과도 비슷한 것 같다.

일일이 모든 경우의 수를 탐색하는 결정론적 알고리즘.

즉, 쉽게 말해서 결정론적 알고리즘은 각 단계에서 다음 단계가 유일하게 결정되고, 비결정론적 알고리즘의 경우 다음 단계가 유일하게 결정되지 않는다.

결정론적 알고리즘은 비결정론적 알고리즘 안에 포함된다. 당연하게도 비결정론적 알고리즘은 결정론적 알고리즘이 할 수 있는 모든 것들을 해낼 수 있기 때문이다.

P,NP는 각각 어떤 문제들의 부분집합이다.

P는 어떤 결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합이고, NP는 어떤 비결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합이다.

실제로는 비결정론적 알고리즘은 존재할 수 없으므로 NP 문제의 경우 다항 시간에 해결할 수 없다. 하지만 정답 여부는 다항시간 내에 해낼 수 있다. 즉, 해결은 어려우나 검산은 쉬운 문제라는 것이다.

$P\sube NP$는 당연하다고 볼 수 있다.

P의 경우 문제 해결이 쉽게 되기 때문에, 모든 경우에 대해 옳고 그름을 판단하는 해결의 부분집합인 특정 경우에 대해 옳고 그름을 판단하는 검산은 당연히 다항 시간 내에 해낼 수 잇다.

그렇다면, 검산이 쉬운 문제는 풀기도 쉬운 문제인가?

이것을 P-NP 문제라고 한다.

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

NP 클래스 안에 있는 모든 문제가 어떤 문제 Q로 다항 시간 내에 환원 가능하다면, 그 문제 Q는 NP-hard이다.

즉, NP 안에 있는 모든 문제들보다 Q가 더 어렵거나, 같다는 것이다.

NP-hard는 아예 해결할 수 있는지 조차도 판별되지 않았다. 그냥 끝판왕 ㄷㄷ

NP-complete의 정의는 NP-hard이면서 NP 안에 있는 경우를 말한다.

즉, NP 안에 속해 있으면서 가장 어려운 문제라는 것이다.

해결될 수 있음은 증명되었으나 개어렵누

2023.03.02 드디어 이해한 것 같다! gg