NP 완전 감소

NP 완전 문제와 관련된 감소에 대해 혼란 스럽습니다. NP에 R과 S의 문제가 2 개 있다고 가정 해 봅시다. 이제 R에 대한 잘 알려진 NP 완전한 문제의 다항식 시간 감소가 있고 S에서 NP 완전한 문제로의 다항식 시간 감소가 있습니다. 문제 R 및 S에 대해 말할 수있는 것은 무엇입니까? NP 완성 또는 NP 하드?NP 완전 감소

출처

2013-02-05 user2044593

이 질문은 프로그래밍에 관한 것이 아니기 때문에 주제를 벗어난 것으로 닫습니다. –

NP 완성 문제가 다항식 시간에서 R로 감소하면 NP의 모든 문제도 해결됩니다. 그러므로 R은 NP-Hard입니다.

S가 NP 완전 문제로 감소하면 S는 NP가됩니다.

반드시 NP 완성이 아니어야합니다. 우리는 R이 NP (어쩌면 그것은 결정할 수 없음)인지 S가 NP-Hard인지 (사소한 것일 수 있는지) 모릅니다.

출처

2013-02-05 20:35:13 Patrick87

그 점에 대해 고마워, 나는 내 마음 속에 또 다른 의심을 품는다. NP에있는 문제 L은 문제로 축소된다. L '.. 그러면 문제에 대해 말할 수있는 것이 무엇인지 L' – user2044593

@ user2044593 물질의 어떤 것도 : L '은 undecidable, NP-Complete, NP가 아니라 NP-Complete (P! = NP라고 가정) 또는 P. 모든 문제는 그 자체로 감소합니다. 이 사소한 경우를 버리더라도 L '과 L이 근본적으로 같은 것을하는 알고리즘에 의해 풀리는 것과 같은 문제 L'을 찾는 것은 어렵지 않습니다. – Patrick87

설명해 주셔서 감사합니다! – user2044593

NP 완전 감소

답변

관련 문제