One-Way Functions and the Berman-Hartmanis Conjecture

被引：4

作者：

Agrawal, Manindra ^{[1
]}

Watanabe, Osamu ^{[2
]}

机构：

[1] Indian Inst Technol, Dept Comp Sci, Kanpur, Uttar Pradesh, India

[2] Tokyo Inst Technol, Dept Math & Comp Sci, Tokyo, Japan

来源：

PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY | 2009年

关键词：

average-case one-way function; P-isomorophism conjecture; P/poly-isomorophism in NP; one-way function with easy cylinder;

D O I：

10.1109/CCC.2009.17

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Berman-Hartmanis conjecture states that all NP-complete sets are P-isomorphic each other. On this conjecture, we first improve the result of [3] and show that all NP-complete sets are <=(p/poly-)(li,1-1)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.

引用

页码：194 / +

页数：2

共 15 条

[1] Pseudo-random generators and structure of complete degrees [J].

Agrawal, M .

17TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2002, :139-147

[2] Reductions in circuit complexity: An isomorphism theorem and a gap theorem [J].

Agrawal, M ;

Allender, E ;

Rudich, S .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1998, 57 (02) :127-143

[3]

AGRAWAL M, 2001, FDN SOFTWARE TECHNOL, P70, DOI DOI 10.1007/3-540-45294-X7

[4]

[Anonymous], 2001, FDN CRYPTOGRAPHY

[5]

Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023

[6] ONE-WAY FUNCTIONS AND THE ISOMORPHISM CONJECTURE [J].

GANESAN, K .

THEORETICAL COMPUTER SCIENCE, 1994, 129 (02) :309-321

[7]

Goldreich O., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P25, DOI 10.1145/73007.73010

[8]

Goldreich O., 2009, TR09028 ECCC

[9]

HASTAD J, 1998, SIAM J COMPUT, P221

[10]

Impagliazzo Russell, 1996, VERY STRONG ON UNPUB

← 1 2 →