결정 문제 다항식 시간의 단축

Question

질문이 있습니다. 우리가 두 가지 결정에 문제가 있다면, L1과 L2라고 말하십시오. L1과 다항식 시간에 L2로 줄일 수 있다면 L2는 다항식 시간으로 L1로 환원 될 수 없다는 것이 사실입니까? L1은 P에 있거나 경우에만 사실이다

이

L1 can be reduced to L2 in polynomial time => NOT (L2 can be reduced to L1 in polynomial time) 
=(L1 not in P) & (L2 in P) => (L1 in P) & (L2 not in P) 
=[(L1 in P) OR (L2 not in P)] OR [(L1 in P) & L2 in P)] 
=(L1 in P) OR (L2 not in P) 

그래서 L1은 polytime에서 L2로 감소 할 수 있다는 문 L2는 polytime에서 L1로 감소 될 수 없음을 의미한다 :

나의 이해는이 의미하는 것입니다 L2가 P에 없다면 그곳에있는 것처럼, 그렇지 않다면 그 문장은 거짓이다.

내 논리가 의미가 있습니까? 조언이나 도움을 많이 주시면 감사하겠습니다. 고맙습니다!

Answer 1

"L 폴리 시간이 L 로 감소하지 않습니다 다음, L 에 L 을 줄일 경우"일반 문은 일반적으로 거짓입니다. P에있는 두 가지 문제 (∅ 및 Σ * 제외)는 서로 다항식으로 시간을 환산 할 수 있습니다. 다항식 시간에 문제를 풀고 예 또는 아니요 대답을 적절하게 출력합니다.

두 가지 문제 사이의 다항식 시간 단축 가능성이 이 아니므로은 언어가 P인지 여부를 보장하지 않으므로 특정 논리가 올바르지 않습니다. 예를 들어 정지 문제는 다항식 시간이 TM이 주어진 문자열을 받아들이는지 여부에 대한 문제로 축소 될 수 있지만 어느 문제도 P에 있지 않으므로 두 가지 문제를 모두 결정할 수 없습니다.

희망이 도움이됩니다.