1
가정 P! = NPNP- 중급 문제 란 무엇입니까?
오일러 다이어그램은 P 및 NP 완성의 일부가 아닌 부분을 보여줍니다. 나는이 세트가 NP- 중급이라고 불리는 위키 피 디아 (위키피디아)를 읽었다.
는 I에 관한 몇 가지 의문은 어떻게 NPI 문제가 정의되어 있나요?
A
답변
2
NP -intermediate 문제는
- 이 에서 NP (즉, "예"라고 답변 다항식 시간에 검증 할 수있다),
- 이 에 있지 않은 의사 결정 문제 P (즉, 문제를 해결하기위한 다항식 시간 알고리즘이 없음)
- 은 NP이 아닙니다.
마지막 기준은 여러 가지 다른 방법으로 기술 할 수 있습니다. 이것을 말하는 한 가지 방법은 SAT에서 특정 문제에 대한 다항식 시간 매핑 감소가 없다는 것입니다. 우리가 하나를 찾을 수 있다면, 우리가 P에없는 문제 NP이있을 것이다 -
이러한 문제는 NP -intermediate 문제가있을 경우 우리가 모르기 때문에 지금은 주로 이론적 인 관심있는, 의미는 입니다. ≠ NP! 우리가 P ≠ NP을 증명할 수있는 경우 때문에, 그들이 흥미있어, 우리는 다항식 시간에 해결하기에 너무 어려운 에서 몇 가지 문제가 NP이 있다는 것을 알고 있지만, 어느 사이에 없습니다 NP의 하드 문제 중 "가장 힘든"(NP- 완료 문제). 당신이 P에 NP에하지만이 문제가 없었기 때문에 P = NP, 그럼 어떤 NP -intermediate 문제가되지 않을 것하는 경우에
. NP P ≠ 경우, 래드 너 정리 보장 적어도 하나의 NP -intermediate 문제가 존재하지만, 특히 고도의 인공하는 문제를 구성하여 그렇게 그 경우 NP -intermediate로 유일하게 디자인했다. 지금, 몇 가지 예외 (특히 graph isomorphism problem)와 함께, 모든 문제는 우리는 NP는 정면 P 또는 NP - 완전한 것으로 알려져에서 하나 에서의 알고.+0
따라서 팩터링과 같은 문제는 NP 또는 중급 원인이 될 수 있으므로 P 또는 NP가 완료되지 않습니다. –
+0
의사 결정 문제가 아니기 때문에 "어떻게하면 k보다 작은 요인이 있습니까?"와 같은 식으로 조심해야합니다. NP-intermediate가 될 수 있습니다. – templatetypedef
당신은 무엇을 가지고 있습니까? –