검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

P-Comp Versus P-Samp Questions on Average Polynomial Domination 평균 다항식 지배에 대한 P-Comp 대 P-Samp 질문

Shin AIDA, Tatsuie TSUKIJI

  • 조회수

    0

  • 이것을 인용

요약 :

평균 사례 NP-완전성 이론에서 Levin은 다항식 지배를 도입했고 Gurevich는 평균 다항식 지배를 도입했습니다. Ben-Davidet al. P-samp(다항식 시간 샘플링 가능 분포 클래스)가 P-comp(다항식 시간 계산 가능 분포 클래스)에 의해 다항식으로 지배된다면 강력한 일방향 함수가 존재하지 않는다는 것을 증명했습니다. 이 결과는 다항식 지배에서 평균 다항식 지배로 가정을 완화함으로써 강화될 것입니다. 우리의 결과에는 (NP,P-samp)에서 (NP,P-comp)까지의 평균 다항식 일대일 환원성에 대한 불완전성도 포함됩니다. 이러한 결과와 기타 관련 결과를 도출하기 위해 Ben-David et al.이 제시한 접두사 검색 알고리즘이 있습니다. 평균 다항식 지배에서 살아남도록 수정됩니다.

발행
IEICE TRANSACTIONS on Information Vol.E84-D No.10 pp.1402-1410
발행일
2001/10/01
공개일
온라인 ISSN
DOI
원고의 종류
PAPER
범주
계산 복잡도 이론

작성자

키워드