NP-Hard, NP-Complete

ㅎㅎ 안녕하세요 :)

이전글에서 P와 NP의 개념에 대해서 아주 길게.. 설명드렸는데...

조금 이해가 가셨나요 ㅠㅠ? 

궁금한점이 있다면 댓글이나 채널서비스를 이용해서 바로 질문해주세요!!

오늘은 NP-Hard와 NP-Complete에 대해서 설명드릴려고 해요.

무서워하지마세요!!!

우리는 그냥 얘네가 어떤건지~~ 그냥 살짝만 알아볼거에요.(과연;)

근데 정말 잘 읽으셔야 합니다. 헷갈리시면 안돼요. 특히 NP와 NP-Hard...

자. NP-Hard가봅시다.

NP-Hard

---

NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 

그 문제 Q는 NP-Hard이다. 

엥;;;;....

reducible..?;;

"축소시킬 수있는"..?...;;;

이게 무슨뜻일까요?;;

지금!! 몰라도 괜찮습니다.

제가 어떻게든 이해하실 수 있게 설명드릴려고 했는데,

 Transformation을 꼭 설명해야만 할 것 같아서..ㅎㅎ

위 그림을 잘 봐주세요.

자, 처음부터 볼게요. x가 들어갑니다. 이 x는 P라는 문제의 인풋이에요.

그리고 T라는 박스를 만나요. 이 T는 Transformation Function입니다.

Transformation Function은 들어온 인풋을 어케어케 해서 아웃풋을 하나 주는데, 그것이 바로 Q의 인풋이됩니다.

즉, Transformation Function은 P의 인풋을 Q의 인풋으로 바꾸어주는 역할을 해요. 

저기 an input for Q라는 것. 보이시죠?

이제 P의 인풋 x는 Transformation Function를 거쳐 Q의 인풋으로 바뀌게 되었습니다. 

이제, 저 Q를 풀 수있는 알고리즘이 있다고 생각해볼게요. 

그래서 원래 P의 인풋이었던 x를 T를 거쳐서 Q를 풀 수 있는 알고리즘에 넣어보았더니,

Yes 또는 No가 나왔어요. 

1. Q를 풀 수 있는 알고리즘에서 Yes가 나왔을 경우. 

 자, Yes가 나왔어요. 그래서 우리는 원래 문제, 즉 P에다가도 Yes를 해봤어요. 

근데 P도 진짜 Yes인거야!!!

2. 1. Q를 풀 수 있는 알고리즘에서 No가 나왔을 경우. 

자, No가 나왔습니다. 그래서 우리는 이 답을 가지고 P한테 No!라는 대답을 줘봤는데 

진짜 No였던거에요.

이걸 모든 인스턴스에 대해 해보게되면, 어떻게될까요?

우리는 Q를 풀 수 있는 알고리즘으로 P를 푼거죠?

맞죠? Algorithm for Q를 돌리니까 대답이 나왔고, 그 대답을 P에 준거니까.

그럼, 간단하게 생각해봤을 때,

P와 Q중에서 어느게 더 "어려운" 문제일까요?

생각해보셨나요?

정답은 Q입니다!

Q를 해결하는 알고리즘으로 결국, P를 푼것이니 Q가 더 어렵다고 할 수 있겠죠?

정확히 말하면, "어렵거나 같다"이지만요. 이 말 뜻은 조금이따가 설명드릴게요.

우리 지금..reducible이야기 하다가..이까지 온거죠..?

설명드리겠습니다.

위와 같은 상황에서 우리는,

"Problem P is reducible to Q"

라고 합니다. 

to 뒤에 있는게 더 "어렵다"고 생각하시면 편해요. (정확히는 어렵거나 같다입니다.)

그럼 NP-Hard의 정의를 다시 볼까요? 

NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다. 

저 말은 Q를 풀 수 있는 알고리즘으로 NP클래스에 있는 모든 문제를 풀 수 있다는 소리겠네요?

간단하게 말하면, NP클래스 안에 있는 모든 문제들보다 Q가 "어렵다"고 할 수 있겠네요.

(다시한번 말씀드리지만, 어렵거나 같다입니다.)

이제 NP-Hard에 대해서 좀 아시겠나요?

지금 헷갈린다고 좌절하지마세요. 

저도 그랬고, 원래 정말 어려운 파트입니다 ㅠㅠㅠ

+ 추가

NP-Hard를 쉽게 정의하자면, 

어떤 certificate를 주면, 그것을 다항시간안에 대답할 수 있으면 그것은 NP였죠?

NP-Hard는 어떤 certificate를 주더라도, 그것을 다항시간 안에 대답할 수 없는 것입니다. 

모든 경우의 수를 일일이 확인해보는 방법밖에 없는 것이죠. 

이거 아닙니다..

만약 어떤 공간에 우리가 다같이 있다고 생각해봐요. 

음...우리는 모두 학생이에요!! (가정)

우리는 학생이랬죠? 우린 지금 NP클래스고,

"어렵다"라는 기준을 나이로 판단한다고 할게요. 즉 나이가 많으면 어려운거라고 합시다.

우리는 지금 NP라는 클래스 안에 있다고 했죠. 그냥 있는데, 

갑자기 어떤 학생이 아닌 나이가 많은 어떤 사람이 있어요. 하지만, 학생은 아닙니다. 즉 NP클래스는 아니지만, 우리보다 나이가 많아요. 즉 어렵다는 거죠?

그 나이가 많은 사람은 NP-Hard가 되는 겁니다.

하지만 갑자기 그 사람이 학생이 됐어요!!!!!!!!

그럼 그 사람은 NP-Complete가 됩니다.

NP-Complete

---

NP-Complete는 간단합니다. 

NP-Hard이면서 NP클래스 안에 있으면 NP-Complete입니다.

NP클래스에 속해있으면서, 어떤 기준에 의해 가장 어려운 문제이면 NP-Complete인거죠.

한 예를 들어볼까요?

음..이반(NP클래스)에서 어떤 학생 4명이 전투력이 가장 높다고 생각해볼게요. 

이 4명은 NP클래스에 있는 어떤 문제들보다도 전투력이 높으니까 

NP-Hard이면서 NP클래스 안에 있으니 NP-Complete입니다.

하지만, 어떤 전학생이 왔어요. (NP클래스 안으로 들어왔어요)

그리고 그 전학생은 자기가 전투력으로 1등이 되고싶은 야망을 가지고있어요.

그러면 어떻게하면될까요?

이 반(NP클래스)에 있는 모든 학생들과 1:1로 싸워보면 될까요?

물론 그 방법도 언젠간 가능하겠죠?

하지만 어느세월에?

정말 간단한 방법이 하나 있죠!

바로 우리반에서 가장 쎈애들과 붙어보면 되는거에요.

그럼 4번만 싸우면 되겠죠?? 훨씬 간단해지는 것이죠.

만약 그 아이들과 싸워서 전학생이 이겼다고 생각해봅시다.

그럼 전학생은 NP클래스에 있는 가장 전투력이 높은 학생을 이긴것이니 (즉, NP클래스에서 가장 어려웠던 문제를 이긴것이니)

제가 가장 어려운, 즉 전투력이 가장 쎈 학생이 되겠죠?

그리고, 가장 중요한 것.

그럼 나머지 4명은 어떻게 될까요? 전학생이 이겼으니 이 4명은 2등이 될까요?

아뇨. 그 4명은 이번에만 졌을 뿐, 

다른방법으로 그 전학생과 싸우면 언젠가는 반드시 이깁니다.

즉 이 반에서 가장 어려운 사람은(전투력이 가장 쎈 사람은) 전학생이 되는 것이 아니라,

5명이 되는 것이죠. 

그러니까!!제가 위에서 계속 언급했다시피, 어렵거나 같다라는 말이 나온 것입니다. 

전학생이 1등들을 이겼다고해서 기존 1등들이 부정되는 것이 아님을 주의하세요. 

그 1등들도 전학생으로 reduce되지만(전학생이 이번에 이겼으니), 

전학생도 그 1등들한테 reduce될 수 있다는 소리입니다.

그러니까 결과적으로 모두 NP-Complete가 된거죠!

그럼, 우리는 지금 싸우는 것으로 예제를 들었지만, 진짜로 어떤 문제가 더 "어렵다"라는 것을 어떻게 증명할까요?

ㅎㅎ 위에서 봤던 이 과정을 이용하면 된답니다.

해볼까요?

증명할 것 : 어떤 문제 P가 Q로 reducible하다. (Q가 더 어렵거나 같다) 

그럼 어렵다는 걸 어디 한번 증명해보자.

우리 위의 전투력 예제에서, 1등과 전학생으로 예를 들었죠? 그러니까 NP클래스안에있는 가장 어려운문제들.

그러니까 문제 P는 NP-Complete인 문제로 골라봅시다. 

근데 어떤 문제 Q는 얘가 NP-Hard인지, NP-Complete인지 몰라요.

전학생도 처음에 왔을 때는 얘가 NP-Hard인지, NP-Complete인지 몰랐던 것처럼요.

그러니까 한번 해보는겁니다. 만약 전학생으로 기존 1등(즉, NP-Complete)이 해결되게 되면, 전학생이 더 어렵다고 할 수 있죠.

정확히는 "어렵거나 같다"이지만요.

그러니까 한번 해보는겁니다.

P의 인풋을 Transformation Function에 넣어서 Q의 인풋으로 바꾸고, 

Q를 풀 수 있는 알고리즘있다고 가정했을 때, 결과를 P에 대봤더니 모두 맞았어요.

그럼 P를 푼거죠? 

근데 한번생각해봅시다. 

P는 분명 NP클래스안에 있는 어떤 문제들보다 어려운 문제였어요. 

근데 위의 방법으로 풀었다?

그럼 NP안에 있는 모든 문제들이 Q로 reducible해집니다. 당연하겠죠?

어? 어디서 익숙한 정의같지 않으세요? 

NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 

그 문제 Q는 NP-Hard이다. 

즉, 우리는 위의 방법으로 Q가 NP-Hard라는 것을 증명한것입니다.

(NP-Complete아니에요!)

전학생이 우리반으로 전학 오기전에 우리반의 1등들과 싸웠다고 생각해봅시다.

전학생이 이겼으면 우리반에서 가장 어려운 1등들과 싸워서 이겼으니 전학생이 더 어렵다는 것이 증명됐죠? 하지만, 전학생은 아직 우리반으로 전학오지 않아서 NP-Complete라고 할 수 없죠. 아직까지는 NP-Hard인것입니다!!

그럼 이 전학생, 즉 Q가 NP클래스 안에 있다는 것은 어떻게 증명하면 될까요?

저번시간에 배웠죠 우리?

어떤 certificate가 다항시간에 verify되면, 그 문제는 NP클래스이다.

그냥 어떤 certificate를 주면 돼요.

그래서 많은 논문들에서도 NP-Hard임을 증명하는 것은 아주 길게 써놓지만,

NP클래스 안에 있다는 것은 아주 쉽게 증명한답니다.

그런데........한가지 중요한 사실이 있습니다.

가정해볼게요.

P의 인풋 x를 Q의 인풋으로 바꾸는 과정이 다항시간 (Polynomial Time)이 걸렸다고 해볼게요.

그리고 Algorithm for Q역시 다항시간(Polynomial Time)이 걸렸다고 가정해봅시다.

그러면, 전체 박스가 다항시간에 풀린거죠? 전체박스는 Algorithm for P인데, 

우리는 그럼 P를 다항시간에 풀게 되는거죠??

근데...

우리가 P를 NP클래스안에있는 어떤문제보다 어려운 문제, 즉 NP-Complete를 골랐다고 해봅시다.

근데 그게 다항시간에 풀렸어;;;

(참고로 NP-Complete문제들은 이때까지 알려진 다항시간 알고리즘이 없습니다...)

근데 다항시간에 풀렸어?!!!!

근데 우리가 어떤 문제를 푸는 다항시간 알고리즘이 있으면 뭐랬죠? 

네. 클래스 P에 속한다고 했죠.

근데 NP-Complete문제가 다항시간에 풀린다?

NP클래스 안에 있는 어떤 문제보다 어려웠던 문제가 다항시간에 풀린다?

그럼 NP클래스 안에 있는 모든 문제를 다항시간에 풀 수 있다?

우리는 P가 NP에 속하는 건 알아요. 

만약 저 모든 과정이 다항시간에 이루어진다면, 

NP가 P에 속하게 되고,

결과적으로 P=NP이게 됩니다. 

ㅎㅎㅎㅎ어떠신가요.

P와 NP의 개념을 몰랐다고 해도,

P-NP문제라는 현재 수학계의 난제를 들어보신분들도 계실거에요.

이 난제는 P집합과 NP집합이 같은지 다른지 증명하는 100만달러가 걸린 문제입니다. 

알려진지 40년이 지났는데도, 현재까지 풀리지 않고 있다고 해요.

간단하게 설명드리자면, P가 NP에 속하는 것은 이미 알려진 사실이죠?

결국 모든 NP문제가 P인가를 증명하면 된답니다. 

그러니까!!!!!!

여러분, 어느!!!정말 현재 알려진 NP-Complete문제들이 정말 너무나도 많은데, 

이중에서 정말 어느 NP-Complete문제 하나라도 다항시간 알고리즘을 만들어내면

모든 NP-Complete문제들이 다항시간에 풀린다는 것을 증명하는 것입니다.

(서로 reduce될 수 있기 때문에)

만약, 이 문제를 풀 수 있는 다항시간 알고리즘은 없다! 라고 증명하면 P!=NP가 되는거죠.

둘 중 어느것을 증명해도 백만달러.

ㅎㅎ..

와.. 길고 긴 NP-Hard, NP-Complete 글이 끝났는데요. 어느정도 이해가 가시나요?

이해가 가지 않는다? 정말 괜찮아요. 제가 너무 어렵게 쓴 탓입니다 ㅠㅠㅠ 

하지만 정말정말 쉽게 설명하려고 노력했어요.

만약 이해가 가지 않으시거나 지적할 부분이 있으면,

댓글이나, 채널서비스(PC화면에서 보임)를 이용해주세요. 

도움이 되었으면 좋겠어요!!!