On one-way functions and polynomial-time isomorphisms
type: Item
instance of: scholarly article
title: On one-way functions and polynomial-time isomorphisms
zbMATH Open document ID: 0635.68038
DOI: 10.1016/0304-3975(86)90152-0
author: Timothy J. Long
author: Du Ding-Zhu
author: Ker-I Ko
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: Two sets A and B are polynomial-time isomorphic if there exists a polynomial-time computable, polynomial-time invertible, one-to-one correspondence f between the domains of the two problems such that \(x\in A\) iff f(x)\(\in B\) for all instances x. On the basis of the observation that all natural NP-complete sets are polynomial-time isomorphic, \textit{L. Berman} and \textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that indeed all NP-complete sets are polynomial- time isomorphic. \textit{D. Joseph} and \textit{P. Young} [Theor. Comput. Sci. 39, 225-237 (1985; Zbl 0597.68042)] noticed that k-creative sets, a new class of NP-complete sets, do not seem to be polyomial-time isomorphic to natural NP-complete sets unless one-way functions do not exist. They conjectured that if one-way functions do not exist then not all NP- complete sets are polynomial-time isomorphic. The existence of one-way functions is, in this paper, related to the question of whether the EXP-complete sets are all polynomial-time isomorphic. It is known that the EXP-complete sets are equivalent under one-one, length-increasing polynomial-time reductions. Using the polynomial version of the Cantor-Schroeder-Bernstein construction, as described in Berman and Hartmanis, it follows that if one-way functions do not exist, then the EXP-complete sets are all polynomial-time isomorphic. It is proved in this paper that the existence of one-way functions is sufficient to distinguish, in the class EXP, between polynomial-time isomorphism and equivalence under one-one, length- increasing reductions. Furthermore, such sets can be made to be truth- table complete for EXP.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4035139
zbMATH Keywords: one-way functions
zbMATH Keywords: NP-complete sets
zbMATH Keywords: EXP-complete sets
zbMATH Keywords: polynomial-time isomorphism
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90152-0
OpenAlex ID: W2078503376
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: TWO CASES OF RECONSTRUCTION OF SEPARABLE GRAPHS
cites work: Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
cites work: On some natural complete operators
cites work: On one-one polynomial time equivalence relations
description: scientific article; zbMATH DE number 4035139