On one-one polynomial time equivalence relations (Q1068536): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Q701619 / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ren-ji Tao / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4162663 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On sparse sets in NP-P / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3862379 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5573961 / rank | |||
Normal rank |
Latest revision as of 10:23, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On one-one polynomial time equivalence relations |
scientific article |
Statements
On one-one polynomial time equivalence relations (English)
0 references
1985
0 references
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.
0 references
p-isomorphic
0 references
polynomial time one-one reductions
0 references
EXPTIME-complete sets
0 references
complexity classes
0 references