文章基本信息

标题：One-Way Functions and the Isomorphism Conjecture
本地全文：下载
作者：Agrawal Manindra ; Osamu Watanabe
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the Isomorphism Conjecture proposed by Berman and Hartmanis. It states that all sets complete for NP under polynomial-time many-one reductions are P-isomorphic to each other. From previous research it has been widely believed that all NP-complete sets are reducible each other by one-to-one and length-increasing polynomial-time reductions, but we may not hope for the full p-isomorphism due to the existence of one-way functions. Here we showed two results on the relation between one-way functions and the Isomorphism Conjecture. Firstly, we imporve the result of Agrawal [Agrawal, CCC'02] to show that if regular one-way functions exist, then all NP-complete sets are indeed reducible each other by one-to-one, length-increasing and P/poly-reductions. A consequence of this result is the complete description of the structure of many-one complete sets of NP relative to a random oracle: all NP-complete sets are reducible each other by one-one and length-increasing polynomial-time reductions but (as already shown by [Kurtz etal, JACM 95]) they are not P-isomorphic. Neverthless, we also conjecture that (different from the random oracle world) all one-way functions should have some dense easy parts, which we call P/poly-easy cylinders, where they are P/poly-invertible. Then as our second result we show that if regular one-way functions exist and furthermore all one-one, length-increasing and P/poly-computable functions have P/poly-easy cylinders, then all many-one complete sets for NP are P/poly-isomorphic.
关键词：hard one-way function , NP , one-to-one length increasing reduction , p-isomorphism conjecture