먼저 P=NP인지 P≠NP인지 아직 밝혀지지 않았고 이걸 풀어내는게 유명한 P-NP문제

먼저 P는 다항(Polynomial) 시간에 문제의 정답을 찾을 수 있는 문제

NP는 다항 시간에 주어진 답이 정답인지 아닌지 확인할 수 있는 문제

여기서 문제, 정답, 시간 등 정의해야 될게 많은데 이건 알고리즘이나 계산이론을 공부하면 나오니까 패스

P문제는 아주 자명하게 NP문제지

왜냐면 문제 자체를 푸는데 걸리는 시간이 다항 시간이니까 어떤 답이 주어지든 다항 시간안에 정답을 찾고 다항 시간안에 주어진 답과 비교하면 되거든

대표적인 P문제는 값들을 순서대로 정렬하는게 있고

주어진 답이 정답인지 확인하는 방법은?

주어진 값을 정렬한다: 다항 시간

정렬한 값을 주어진 답과 비교한다: 다항 시간

따라서 정렬은 주어진 답이 정답인지 확인하는 시간이 다항 시간이기 때문에 NP문제

(주어진 값이 순서대로 정렬되었는지 비교하는건 사실 값의 개수만큼 비교 연산을 하면 되지만 P, NP의 정의에서는 다항 시간이기만 하면 되서 상관없음)

갑자기 귀찮아서 여기까지만 적음

궁금하면 유튜브에 P-NP문제 검색하면 잘 요약한 동영상들 많으니까 찾아보셈