나는 P, NP, NP-Complete 및 NP-Hard를 직관적 인 방식으로 랩핑하려고 노력하고있어 그 정의를 기억할 필요가 없습니다.일부 NP-Complete 문제는 어떻게 NP-Hard가 될 수 있습니까?
다음 이미지 (왼쪽 시나리오, P! = NP)에는 NP-Complete와 NP-Hard 사이에 겹치는 영역이 있습니다. 일부 문제는 NP-Complete 및 NP-Hard라는 것을 의미합니까? 나는이 모순 된 대답을 발견한다.이 특별한 대답에 따르면 : What are the differences between NP, NP-Complete and NP-Hard?.
위의 표에는 다항식 시간에 NP- 완전 문제를 확인할 수 있으며 NP- 하드 문제는 없다고 나와 있습니다. 그렇다면 오버랩은 어떻게 될 수 있습니까? NP-완전성의 정의의
부분은 하드 순이익되고 있습니다. 따라서 모든 NP 완전 문제는 NP 어렵다. 이것은 또한 두 그래프 모두에 반영됩니다.
몇 시간 전에 고칠 때까지 연결된 테이블이 잘못되었습니다. NP- 완전 문제는 NP 문제의 부분 집합이며 모든 NP 문제는 정의에 따라 다항식 시간으로 검증 가능합니다. NP-hard 문제는 적어도 다른 NP 문제 (NP에없는 문제는 NP 하드 일 수 있기 때문에 일종의 직관력이없는 문제)입니다.
가 NP에특정 복잡 클래스에 완료하기 위해, 문제가해야 문제가해야
는 NP-완료하려면우리는 "적어도 어렵다고 정의해야합니다. NP에 A 문제가 있다고 가정 해보십시오. NP-hard (따라서 NP-Complete)임을 증명하기 위해 NP의 모든 문제가 다항식 시간에 A로 변환 될 수 있음을 보여줍니다. A는 적어도 푸는 데 다항식 시간이 걸리므로 다항식도 추가로 닫히기 때문에 변환은 이제 무시할 수 있으며 런타임은 A의 런타임과 동일합니다 (다항식이든 아니든간에).
일단 NP 완성 문제가 발생하면 NP 문제가 B에 속하며 다항식 시간에 A로 변환하여 NP에서 NPI가 문제이므로 (NP 완성) 문제를 증명할 수 있습니다.
이것은 NP-Complete가 NP 하드의 하위 집합이며 (연결된 테이블이 잘못 되었음) 분명히하기를 바랍니다.
링크 된 답변은 다른 답변과 모순되며, 위키 피 디아의 이미지와 연결하면 스스로 모순됩니다. 귀하의 질문은 답을 명확히하기 위해 후속 의견으로 제시하는 것이 가장 좋습니다. (그리고 당신이 그 정의를 기억할 때까지, 나는 당신이 그들 주위에 당신의 머리를 전혀 싸지 않았다는 것을 주저하고 싶다.) –
@RobKennedy, done. – Srikanth