NP-Hard, NP-Complete가 무슨 의미인지 설명해주실 수 있나요?

오늘 학부생 한 아이가, "NP-Hard, NP-Complete가 무슨 의미인지 설명해주실 수 있나요?" 하는 질문을 해왔는데,

설명이 잘 된 것 같아서, 그리고 혹시 내가 틀린 부분이 있다면 피드백을 기대하는 마음에 정리를 해보고자 한다.

1.

우리가 고등학교 때는, 그 2차 함수를 풀기 위한(정점, 내지 저점을 찾아가는 문제라고 할 때ㅎ) 방법이 아주 명료했어요. 변수가 x라면, x에 대해서 풀어주면 되었거든요.

그런데, 실제 최적화 문제는 이렇게 푸는 방법이 명료하지 않은 경우가 굉장히 많고, 그럴 때 풀어보는 방법 중 하나는, 그 x값에 가능한 모든 값을 다 대입해보는 것이 될 수 있어요.

그런데 만일 correct한 x값이 0.333333.. 뭐 이런 상황이었다던지

그림과 같은 상황에서라면, 알고리즘을 짜기에 따라서는, local optimization값을 찾아가게 만들어놨더니, 저런 빨간 점에서 찾아나가기 시작했더니, 저 작은 봉우리 정점까지는 찾아가놓고, 더이상 움직이지 않는다던지 등등, 이런 경우에는 정말 옳은 해를 찾기 어려울거에요.

그런데 이건 어쩔 수 없는게, 컴퓨터 메모리 문제라던지, 저 봉우리가 워낙 많은데 알고리즘을 개발하기 어렵다던지 여러가지 문제로 인해 어려움이 생길 수 있고, 이렇게, 실제 값을 찾기는 어렵고, local 최적화를 할 수 밖에 없는 그런 상황을 NP-Hard 문제라고 해요.

1a. ( - 학생의 추가 질문: "로컬 최적화가 무슨 의미인가요?" )

저 위의 그림 같은 경우, 우리가 2차 함수를 푸는 방법밖에 모르는 상황이라고 해봅시다.

그러면 저 포물선 2개를 잘라서 볼 수 있겠죠?

왼쪽 포물선 "지역"만 풀어보고, 오른쪽 포물선 "지역"만 또 따로 풀어보고

이렇게 일부만 잘라서 풀어보는걸 제가 local 최적화라고 표현한거에요.

최단거리 알고리즘 같은거 공부한 적이 있나요? 최단거리문제 같은 경우에도, 전체를 스캔하기 어려우니까, 일부 node에서 시작하면서, 자기 주변만 살펴보면서 훑어나가는 방법이 있죠? 그렇게 "볼 수 있는 부분"을 조금씩 조금씩 훑어나가는 것도 local optimization 방법이라고 할 수 있죠.

1b.

node와 거리 개수가 많을 때 그 알고리즘을 돌려봤는지 모르겠는데, node 개수가 적고 할 때는 그런 방법으로도 답이 얼추 맞을 수 있지만, 거리가 많고 node도 많고 복잡해지고 하면 그게 정답을 잘 못찾아내는 경우가 많아요.

하여튼, global한 해를 못찾기 때문에 local 해를 찾아나갈 수밖에 없는 경우 이 경우 대체로 global한 해를 찾기 어렵다고 해요. 못푼다고 증명이 되었다고 한 것 같은데, 아마 미국 어디 수학연구에서 수학 몇 대 난제 중 첫 번째 문제인가?

네 이런 경우를 NP-Hard한 문제라고 불러요.

( - 학생 답변: "위키백과를 검색하니까 np에 속하는 모든 판정문제를 다항시간에 다대일 환산할수 있는 문제의 집합이다 이렇게 나와있는데, 정의에 나온 다대일 변환이 결과적으론 로컬 최적화랑 매치되는거네요"

- 내 답변: "오 맞아요." )

2.

NP-complete는 답이 있는지 없는지 알수는 없는 상황이에요~ 그렇지만 여러 번 반복해서 풀어야함은 자명한 상황이지요.

가령 "점이 여러 개 있다. 이를 한 번 선긋기로 모든 점을 이을 수 있을까?"

NP-Hard의 문제 중 하나로 제가 최단거리 알고리즘이라고 얘기해줬었는데, 이건 딱 봐도, "분명 어딘가 최단거리는 존재한다"고 확신할 수 있죠? 누구도 부정할 수 없을거고요.

그런데 NP-Complete는 그것조차 확신하기 어려운 경우에요. 위에서 이야기한 "점이 여러 개 있다. 이를 한 번 선긋기로 모든 점을 이을 수 있을까?" 이런 문제라면, 이건 쉽게 풀기 어려워요. 해답이 "그런 경우도 있고 아닐수도 있다"이니까요. 그렇지만 여러 번 반복해서 그려보기는 해야할거고요.