np-hard?

Question

최근에 p vs np 문제에 대해 처음 접했는데 np-hard라는 것에 대해 궁금한 점이 있습니다.np-hard에 대한 설명을 보면 '모든 np문제가 어떤 문제 a로 다항 시간 내에 변환 가능하면 a를 np-hard라고 한다.' 라고 되어 있더군요. 제가 이해한 게 맞다면.. 해밀턴 경로 문제는 np-hard문제이니까 해밀턴 경로 문제를 다항시간 내에 풀어낸다면 이 세상에 존재하는 모든 np 문제를 다항시간 내에 풀 수 있게 된다는건가요? 제가 제대로 이해를 한 게 맞는지 모르겠네요.

Magritte · Answer

아뇨 해밀턴 문제처럼 방법을 알면 다항 시간 내로 풀 수 있는 것도 있지만 답 자체가 있는지도 모르는 것도 있습니다. 또 np문제가 해일턴 문제 유형만 있는 것도 아닙니다. 그게 있는지 없는지 아직 모릅니다.그래서 p=np 이 문제가 아직까지 미해결이죠

성실이 · Answer

맞습니다. 그것을 Np complete 이라고 합니다

핸호 · Answer

모든 np 문제가 np-hard로 변환할 수 있다고 해서, np-hard 문제를 np 문제로 변환할 수 있는건 아닙니다.np-hard는 좀 더 넓은 범위의 문제로, np-hard 범위 안에 np-complete 범위의 문제들이 포함되어 있습니다.np-complete의 정의야말로 &#34;모든 np 문제가 np-complete로 변환될 수 있고, np-complete는 곧 스스로 np 문제이기도 함&#34;입니다.즉 np-complete 문제들은 그들 자체가 np 문제이자, 서로 간에 변환이 가능한 문제입니다.예시로 들어주신 해밀턴경로문제는 np-hard 이기도 하지만, 더 중요한 사실은 np-complete 문제라는 사실입니다. 해밀턴경로를 다항시간안에 풀 수 있는 알고리즘을 발견했다면, 모든 np-complete 문제들은 해밀턴경로문제로도 변환이 가능하고 즉 모든 np-complete 문제를 해결 가능해지는거죠.

np-hard?

3개의 답변

#np-hard 목록