P에서 NP로 축소가 가능합니까?

X가 Y에 폴리 시간 감수성이면 Y가 NP 하드 일지라도 X에 대해 아무 것도 말할 수 없으므로 일부 NP 시간 문제를 해결할 수있는 몇 가지 폴리 시간 문제가 존재해야합니다. 누군가 예제를 제공 할 수 있습니까?P에서 NP로 축소가 가능합니까?

빈 언어가 빈 언어 환원 많은 한 유일한 언어,
이며, 전체 언어는 전체 언어 환원 많은 한 유일한 언어입니다.

다른 개의 언어 Y에는 Y 요소가 있으며 Y의 보수 요소가 있습니다. 모든 들어

는

solve the input 
if the answer is yes: 
    output y 
else: 
    output z

가있다, Y의 보수의 모든 요소 z 용, Y의 모든 요소 y를위한
, 비어 있지 않은 모든 비 전체 언어 Y에 대해 풀 수있는 문제 X를 polytime X에서 Y로 폴리 - 시간 감소.

2016-10-19 04:22:38

답변