증거 NP 완료

Question

안녕하세요 여러분 께 질문이 있습니다. 아무도 그것을 증명할 줄 안다면 궁금합니다.

다음은 질문입니다. 부분 집합 합계 문제는 NP 완료로 표시됩니다. 입력은 양수 w1, ..., wn, W의 시퀀스입니다. 여기서 W는 목표 가중치입니다. 문제는 목표 가중치와 같은 가중치의 합이되도록 (즉, w1 + ... + wi = W) 가중치 F ⊆ {1, ..., n}의 집합이 있는지를 결정하는 것입니다.
Restricted Subset Sum 문제를 Subset Sum과 같이 정의하지만, 목표 가중치가 모든 가중치의 합계의 절반보다 작은 추가 요구 사항을 부여합니다. (이것이 실패하면 즉시 입력을 거절해야합니다.) Restricted Subset Sum이 NP 완성임을 나타냅니다.
감사합니다.

Answer 1

(a) 문제가 NP이고 (b) 문제가 NP 하드임을 보여줘야합니다. (a)의 경우, NP의 일부 문제에 대한 해결책은 문제를 쉽게 해결할 수 있음을 보여줍니다 (생각하면 사소한 것임을 나타냄). (b)에 대해서, 당신은 문제에 대한 해결책이 NP에서의 어떤 문제를 쉽게 풀 수 있음을 보여줄 필요가있다. (다시 말해서 문제에 대한 해결책으로 풀이 될 수있는 또 다른 NP 완전 문제를 찾는다.)

이것은 이미 사실상 절반의 증거입니다. - (a) 이제는 사소한 것입니다. 나머지는하지 않는 것이 좋습니다.