P는 P-Complete와 같은가요?

Question

P는 Complexity Theory에서 P-Complete와 동일합니까? 두 클래스가 동일한 지 알아야합니다. 나는 둘 사이에 Karp 감소가 있기 때문에 인터넷에서 찾을 수 없습니다.

Answer 1

P의 모든 문제가 P.

에 거의 다른 문제 (많은 하나 튜링 모두) "거의"라고하는 유일한 이유가 감소 다항식 시간이 될 수 있습니다 다른 문제가 많지 않을 수있는 하나의 문제 (그리고 그 보완)가 있으므로 (비록 Turing이 줄어들지 만) 모든 것을 허용하는 문제 (모든 것을 거부하는 문제)가 있습니다.

출처 : Wikipedia P-완전성, 다항식 시간 환원에 비해 감소 약한 형태에 대해 이야기 할 때 일반적으로 나열된 이유에 사용되는