IEICE TRANSACTIONS on Information
P-Comp Versus P-Samp Questions on Average Polynomial Domination
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E84-D No.10 pp.1402-1410
- Publication Date
- 2001/10/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Computational Complexity Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
