On one-one polynomial time equivalence relations
type: Item
instance of: scholarly article
title: On one-one polynomial time equivalence relations
zbMATH Open document ID: 0582.68016
DOI: 10.1016/0304-3975(85)90218-X
author: Osamu Watanabe
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: Two sets A and B are said to be p-isomorphic (A\(\equiv B)\) if there is a bijection f such that f and \(f^{-1}\) are polynomial time one-one reductions from A to B and from B to A, respectively, and to be pseudo p- isomorphic \((A\equiv_ pB)\) if there are polynomial time length increasing one-one reductions from A to B and from B to A. \textit{L. Berman} and \textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that all NP-complete (EXPTIME-complete or PTAPE- complete) sets are p-isomorphic, and showed that if \(A\equiv_ pB\) by invertible reductions then \(A\equiv B.\) In this paper it is proved that all EXPTIME-complete sets are pseudo p- isomorphic. So it follows that if the inverse of each length increasing polynomial time injection is polynomial time computable then all EXPTIME- complete sets are p-isomorphic. This result is also extended to many complexity classes, for example, k-SUBEXPTIME and DTAPE(S(n)), where \(k>0\) and S(n) is a tape constructible function with \(S(n)>p(n)\) for almost all n and for any polynomial p(n). In addition, this paper gives some nontrivial examples in EXPTIME-P which show the difference between one-one and many-one polynomial time equivalence relations.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 3932386
zbMATH Keywords: p-isomorphic
zbMATH Keywords: polynomial time one-one reductions
zbMATH Keywords: EXPTIME-complete sets
zbMATH Keywords: complexity classes
reviewed by: Tao Renji
MaRDI profile type: Publication
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Q4162663
cites work: On sparse sets in NP-P
cites work: Q3862379
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Q5573961
Recommended article: On one-way functions and polynomial-time isomorphisms
Recommended article: Complete Problems and Strong Polynomial Reducibilities
Recommended article: One-way functions and the isomorphism conjecture
Recommended article: Every polynomial-time 1-degree collapses if and only if P = PSPACE
Recommended article: Isomorphisms and 1-L reductions
Recommended article: The isomorphism conjecture for NP
Recommended article: On the p-isomorphism conjecture
Recommended article: Q3483270
Recommended article: Collapsing degrees
Recommended article: Productive functions and isomorphisms
description: scientific article; zbMATH DE number 3932386