ZeddiOS

안녕하세요 :) Zedd입니다. 에서, NP-Hard의 정의는"NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다." 라고 말씀드렸어요. 근데, 인터넷에 NP-Hard의 정의를 찾아보시면 이런글들이 엄청나게 많습니다. 저도!!! 저 글에 이렇게 써놨었어요. 이렇게요. 근데..오늘 지하철을 타면서 문득 "NP클래스 안에 있는 모든 문제가 어떤 문제(Q)로 reducible하면, 그 문제 Q는 NP-Hard이다."이거랑,"NP-Hard는 어떤 Certificate를 주더라도 그것을 다항시간에 대답할 수 없다."이거랑 뭔상관이지???라는 궁금증이 들었습니다... 솔직히 서로 하나도 상관없잖아요. 근데 둘다 NP-..