On one-one polynomial time equivalence relations

DOI10.1016/0304-3975(85)90218-XzbMath0582.68016MaRDI QIDQ1068536

Osamu Watanabe

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexity classesEXPTIME-complete setsp-isomorphicpolynomial time one-one reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

One-way functions and the isomorphism conjecture ⋮ Collapsing degrees via strong computation ⋮ A comparison of polynomial time completeness notions ⋮ On one-way functions and polynomial-time isomorphisms ⋮ On resource-bounded instance complexity ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ Isomorphisms and 1-L reductions ⋮ DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ Collapsing degrees ⋮ Notes on polynomial levelability ⋮ A survey of one-way functions in complexity theory ⋮ Complete problems and strong polynomial reducibilities ⋮ E-complete sets do not have optimal polynomial time approximations ⋮ On sets polynomially enumerable by iteration ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ Exponential-time and subexponential-time sets ⋮ On the p-isomorphism conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• On sparse sets in NP-P
• On Isomorphisms and Density of $NP$ and Other Complete Sets