NP-complete 대 NP-hard (이유가 동일하지 않은 이유)

Question

NP- 하드가 NP 완성과 다른 이유는 무엇입니까? 정의의

내 비공식적 인 이해는 사용 :

NP를 -

NP-완전한 다항식 시간에 검증 할 수있는 모든 문제 - NP와 NP-어려운 모든 문제를

NP 하드 - 적어도 NP에서 가장 어려운 문제만큼 어렵습니다.

의사 결정 문제 - 입력과 관련하여 질문을하고 bool 값을 출력하는 문제

혼란 : NP 우리가 증명 또는 NP에있는 모든 문제는 다항식 시간에 해결할 수있는 반증 수 없다는 사실에서 발생하는 대 P의 알 수없는 솔루션

문제. 비슷한 질문이 NP-complete 대 NP-hard에서 발생하는 것처럼 느껴집니다. NP-hard의 모든 문제가 다항식 시간에 검증 될 수 없으므로 NP-hard = NP-complete가되는 것을 어떻게 알 수 있습니까?

다음은 구분이 의사 결정 문제를 함께 할 수있는 뭔가 (내가 전적으로 새로운 해요하지만 충분히 간단 보인다 개념)가 보인다 온라인 연구에서 추론

의 내 라인입니다. 이것은 NP의 문제는 입력이 문제의 해결책인지 묻는 보완적인 결정 문제를 가지고 있음을 의미한다고 생각합니다. 문제는 최적의 솔루션을 찾는 것입니다. 나는 보완적인 의사 결정 문제가 "주어진 입력이 최적의 해법인가?"라고 믿는다. 그리고이 결정 문제가 다항식 시간에서 증명 될 수 있다면 그 문제는 NP 완전 (또는 NP에서)이라고 믿는다. 이것은 NP 완성 문제가 아닌 NP 어려운 문제는 의사 결정 문제가없는 것입니다. (임의의 무차별 대책이이를 해결할 수 있기 때문에 절대로 사실이 아닙니다.) 또는 문제가 NP가 아닌 NP입니다. - 다항식 시간에 검증 할 수없는 결정 문제가있는 경우 완료하십시오. 후자라면 P 대 NP와 같은 문제가있는 것처럼 느껴진다. 즉, NP-hard의 모든 결정 문제가 다항식 시간 솔루션을 가지고 있지 않음을 어떻게 확인합니까?

위의 구절이 이상한 경우 죄송합니다. 나는 내 질문에 혼란을 분명히하려고 노력할 것이다.

노트

내가 직관적 인 설명과 공식적인 설명 (그것은 복잡한 대답 경우 증명) 모두에 관심이 있어요. 공식적인 설명은 분명히 학술 논문에 대한 링크 일 수 있습니다. 나는 누군가가 내 이해의 범위를 넘어서는 지나치게 복잡한 증거에 많은 시간을 투자하기를 원하지 않는다. (나는 복잡성 이론이 매우 빨리 복잡 해지는 것을 발견했다.

설명의 편의를 위해 도움이된다면 여행 판매원 문제를 해결하고 현재 간호사 스케줄링 문제에 대한 논문을 작성 중입니다. (NP 문제는 아닙니다.)

Answer 1

NP 하드에는 다항식 오버 헤드가있는 NP의 문제를 해결하는 데 사용할 수있는 모든 문제가 포함됩니다.

여기에는 이 (가) NP에없는 많은 문제가 포함됩니다.예를 들어, 정지 문제 - 결정 불가능한 문제 - NP-하드이며, NP의 모든 문제는 다항식 시간에 감소 할 수 있기 때문에 :

1. 는 NP-전체 문제의 인스턴스에 NP에 문제를 줄입니다 3-SAT
2. 모든 할당을 검사하고 만족스러운 할당이 발견되면 중단하는 TM을 다항식 시간으로 구성합니다.
3. 중단 문제에 대한 해결 방법을 사용하여 TM이 중지되는지 확인하십시오.
4. 중단 된 경우 받아들입니다. 그렇지 않으면 거부합니다.