| [ QuizWit ] in KIDS 글 쓴 이(By): fox (혼 돈) 날 짜 (Date): 1999년 2월 2일 화요일 오전 08시 19분 17초 제 목(Title): Re: [질문] NP hard/NP complete 머 손쉽게 생각해서 problem set (문제들의 집합... 문제아들의집합?) A에 대해서 A의 모든 problem보다 어려운걸 A-hard라고 하고(A에 속할필요 없음) 문제 b를 해결하면 A를 모두 해결한거나 진배 없으면 b를 A-complete이라고 합니다. 단 b는 A에 속하구요... (저기서 어려운..이라는 말은 애매하지만 어짜피 '해결한거나 진배없음'이나 '어려운'이나 다 transform으로 설명하는 거니까 넘어갑시다) 즉 A hard는 A보다 어려운 거 A complete은 A의 대표격 문제의 어려움이 linear하게 비교가 가능하다면 항상 A complete은 A hard지요... 허나 실제로는 증명을 해야되는걸로 알고 있는데..쩝... 이부분 잘 모름.... 하여튼 뭐 대강 이렇게 알면 될거 같은데요... |