P-NP
컴퓨터로 푸는 문제라는 것은 무엇일까?
문제의 엄밀한 정의는 “입력 집합과 해답 집합 사이의 어떤 관계”라고 할 수 있겠다.
그런데 수많은 형태를 지닌 문제들을 모두 고려하는 것은 쉬운일이 아니기에 입력이 참 또는 거짓인지만 다지는 결정 문제에 대해서만 생각해보려고 한다.
\[S:=\lbrace true, false \rbrace\]사실, 결정 문제만으로도 임의의 문제를 표현하는데는 큰 문제가 없다고 한다; 증명을 포함한 추가 내용들은 더 공부해보아야 할 것 같다.
다항 시간 알고리즘
알고리즘이 입력의 다항시간 안에 해결될 때, 이를 효율적인 알고리즘이라고 부른다.
다항시간이란 시간복잡도가 주어진 입력의 크기 $n$에 대한 적절한 다항식으로 표현될 수 있다는 것이다. $2^n$과 같은 시간복잡도는 지수 시간이며, 효율적인 알고리즘이 아니다.
결정론적 vs 비결정론적
https://gazelle-and-cs.tistory.com/64
위 블로그의 예시가 정말 좋은 것 같다.
여러가지 경우의 수를 동시에 계산할 수 있는, 여러가지 풀이 가능성을 고려할 수 있는 비결정론적 알고리즘. 마치 휴리스틱과도 비슷한 것 같다.
일일이 모든 경우의 수를 탐색하는 결정론적 알고리즘.
https://blog.naver.com/jinp7/222068113705
즉, 쉽게 말해서 결정론적 알고리즘은 각 단계에서 다음 단계가 유일하게 결정되고, 비결정론적 알고리즘의 경우 다음 단계가 유일하게 결정되지 않는다.
결정론적 알고리즘은 비결정론적 알고리즘 안에 포함된다. 당연하게도 비결정론적 알고리즘은 결정론적 알고리즘이 할 수 있는 모든 것들을 해낼 수 있기 때문이다.
P and NP
P,NP는 각각 어떤 문제들의 부분집합이다.
P는 어떤 결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합이고, NP는 어떤 비결정론적 알고리즘으로 다항 시간에 해결할 수 있는 문제들의 집합이다.
실제로는 비결정론적 알고리즘은 존재할 수 없으므로 NP 문제의 경우 다항 시간에 해결할 수 없다. 하지만 정답 여부는 다항시간 내에 해낼 수 있다. 즉, 해결은 어려우나 검산은 쉬운 문제라는 것이다.
P vs NP
$P\sube NP$는 당연하다고 볼 수 있다.
P의 경우 문제 해결이 쉽게 되기 때문에, 모든 경우에 대해 옳고 그름을 판단하는 해결의 부분집합인 특정 경우에 대해 옳고 그름을 판단하는 검산은 당연히 다항 시간 내에 해낼 수 잇다.
그렇다면, 검산이 쉬운 문제는 풀기도 쉬운 문제인가?
이것을 P-NP 문제라고 한다.
NP-Hard and NP-Complete
NP-hard의 정의는 다음과 같다.
NP 클래스 안에 있는 모든 문제가 어떤 문제 Q로 다항 시간 내에 환원 가능하다면, 그 문제 Q는 NP-hard이다.
즉, NP 안에 있는 모든 문제들보다 Q가 더 어렵거나, 같다는 것이다.
NP-hard는 아예 해결할 수 있는지 조차도 판별되지 않았다. 그냥 끝판왕 ㄷㄷ
NP-complete의 정의는 NP-hard이면서 NP 안에 있는 경우를 말한다.
즉, NP 안에 속해 있으면서 가장 어려운 문제라는 것이다.
해결될 수 있음은 증명되었으나 개어렵누
2023.03.02 드디어 이해한 것 같다! gg
https://zeddios.tistory.com/178
https://zeddios.tistory.com/93
https://velog.io/@hysong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-P-NP-%EB%AC%B8%EC%A0%9CP-NP-Problem
https://jusths.tistory.com/122
https://gazelle-and-cs.tistory.com/64