태그 보관물: polynomial-time

polynomial-time

드문 드문 완전 세트 및 P 대 L 축소에서 희소

Mahaney ‘s Theorem은 다항식 다 대다 축소에서 희소 완전 세트 가 있으면 라고 말합니다 . ( ” NP의 스파 스 전체 세트 : Berman과 Hartmanis의 추측 솔루션 “참조)

NP

P=NP

다른 복잡한 클래스에 대해 희소 한 완전한 세트가 존재하는 것으로 알려진 결과가 있습니까? 특히, 로그 공간 다원 감소 아래에 희소 세트 가있는 경우 을 의미 합니까?

P

P=L

답변

그렇습니다. 정확히 제안한 것은 사실입니다. 로그 공간 다수의 축소에서 희소 한 -완전한 세트가있는 경우 입니다. 이것은 1978 년 Hartmanis에 의해 추측되었고 1995 년에 Cai와 Sivakumar에 의해 입증되었습니다 . 이 백서를 참조하십시오 .

P

P=L

하르트 마니 스는 또한 로그 공간 다수의 감소 로 희소 한 -완전한 세트 가 있다면 , 이라고 추측했다 . 이것은 1997 년 Cai와 Sivakumar에 의해 입증되었습니다. 이 다른 논문을 참조하십시오 .

NL

NL=L

답변