NP-Hard의 잘못된 정의

안녕하세요 :) Zedd입니다. 

< NP-Hard, NP-Complete >에서, NP-Hard의 정의는

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

그 문제 Q는 NP-Hard이다."

라고 말씀드렸어요.  

근데, 인터넷에 NP-Hard의 정의를 찾아보시면 이런글들이 엄청나게 많습니다. 

저도!!! 저 글에 이렇게 써놨었어요.

이렇게요.

근데..오늘 지하철을 타면서 문득 

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

그 문제 Q는 NP-Hard이다."

이거랑,

"NP-Hard는 어떤 Certificate를 주더라도 그것을 다항시간에 대답할 수 없다."

이거랑 뭔상관이지???

라는 궁금증이 들었습니다...

솔직히 서로 하나도 상관없잖아요. 근데 둘다 NP-Hard의 정의라고 나온다?

이 둘 사이의 상관관계가 있는건지, 있다면 어떤 상관관계인지 궁금한데..

이걸 물어볼 사람이 없는 겁니다.......

그래서 교수님께 메일을.. 드렸고 방금 답장을 봤어요!! XD

정말... 저는 바보였던겁니다...ㅂㄷㅂㄷ

혹시 < NP-Hard, NP-Complete >에 있던, 

이 그림. 기억하시나요?

그렇습니다.. NP-Hard는 NP에 속하는 문제들도 포함하고 있기 때문에 여기에 속하는 문제들은 Verification이 다항시간에 이루어지는 것이죠!!!!

여기에 속하지 않는 부분들이 "Certificate를 주더라도 그것을 다항시간에 대답할 수 없다."라고 할 수 있겠네요.

 

바로 저 빨간색으로 칠한 부분...

그러니까, Certificate를 주더라도 그것을 다항시간에 대답할 수 없다라는 NP-Hard의 정의는 굉장히 잘못된 것이죠. 

NP-Hard안에는 다항시간에 Verification이 되는 NP-Complete도 있으니까요 :) 

아 조금만 더 생각해봤으면 알 수 있었을텐데 ㅠㅠㅠ 아무튼!!! NP-Hard의 잘못된 정의가 인터넷에 굉장히 많은데..주의하세요!!

오늘도 도움이 되었으면 좋겠습니다 :)