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
평균 사례 NP-완전성 이론에서 Levin은 다항식 지배를 도입했고 Gurevich는 평균 다항식 지배를 도입했습니다. Ben-Davidet al. P-samp(다항식 시간 샘플링 가능 분포 클래스)가 P-comp(다항식 시간 계산 가능 분포 클래스)에 의해 다항식으로 지배된다면 강력한 일방향 함수가 존재하지 않는다는 것을 증명했습니다. 이 결과는 다항식 지배에서 평균 다항식 지배로 가정을 완화함으로써 강화될 것입니다. 우리의 결과에는 (NP,P-samp)에서 (NP,P-comp)까지의 평균 다항식 일대일 환원성에 대한 불완전성도 포함됩니다. 이러한 결과와 기타 관련 결과를 도출하기 위해 Ben-David et al.이 제시한 접두사 검색 알고리즘이 있습니다. 평균 다항식 지배에서 살아남도록 수정됩니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Shin AIDA, Tatsuie TSUKIJI, "P-Comp Versus P-Samp Questions on Average Polynomial Domination" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 10, pp. 1402-1410, October 2001, doi: .
Abstract: In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_10_1402/_p
부
@ARTICLE{e84-d_10_1402,
author={Shin AIDA, Tatsuie TSUKIJI, },
journal={IEICE TRANSACTIONS on Information},
title={P-Comp Versus P-Samp Questions on Average Polynomial Domination},
year={2001},
volume={E84-D},
number={10},
pages={1402-1410},
abstract={In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.},
keywords={},
doi={},
ISSN={},
month={October},}
부
TY - JOUR
TI - P-Comp Versus P-Samp Questions on Average Polynomial Domination
T2 - IEICE TRANSACTIONS on Information
SP - 1402
EP - 1410
AU - Shin AIDA
AU - Tatsuie TSUKIJI
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2001
AB - In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.
ER -