loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2009 24th Annual IEEE Conference on Computational Complexity
One-Way Functions and the Berman-Hartmanis Conjecture
Paris, France
July 15-July 18
ISBN: 978-0-7695-3717-7
ASCII Text
x 
 
Manindra Agrawal, Osamu Watanabe, "One-Way Functions and the Berman-Hartmanis Conjecture," Computational Complexity, Annual IEEE Conference on, pp. 194-202, 2009 24th Annual IEEE Conference on Computational Complexity, 2009.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2009.17,
author = {Manindra Agrawal and Osamu Watanabe},
title = {One-Way Functions and the Berman-Hartmanis Conjecture},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2009},
isbn = {978-0-7695-3717-7},
pages = {194-202},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2009.17},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - One-Way Functions and the Berman-Hartmanis Conjecture
SN - 978-0-7695-3717-7
SP194
EP202
A1 - Manindra Agrawal,
A1 - Osamu Watanabe,
PY - 2009
KW - average-case one-way function
KW - P-isomorphism conjecture
KW - P/poly-Isomorphism in NP
KW - one-way function with easy cylinder
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
The Berman-Hartmanis conjecture states that all NP-complete sets are P-isomorphic each other. On this conjecture, we first improve the previous result of Agrawal and show that all NP-complete sets are P/poly-time computable 1,li-reducible to each other based on the assumption that there exist regular one-way functions that cannot be inverted by randomized polynomial-time algorithms. Secondly, we show that, besides the above assumption, if all one-way functions have some easy part to invert, then all NP-complete sets are P/poly-isomorphic to each other.
Index Terms:
average-case one-way function, P-isomorphism conjecture, P/poly-Isomorphism in NP, one-way function with easy cylinder
Citation:
Manindra Agrawal, Osamu Watanabe, "One-Way Functions and the Berman-Hartmanis Conjecture," ccc, pp.194-202, 2009 24th Annual IEEE Conference on Computational Complexity, 2009
Usage of this product signifies your acceptance of the Terms of Use.