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 classes; EXPTIME-complete sets; p-isomorphic; polynomial time one-one reductions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

Related Items

On the p-isomorphism conjecture, A comparison of polynomial time completeness notions, On one-way functions and polynomial-time isomorphisms, Isomorphisms and 1-L reductions, Collapsing degrees, Notes on polynomial levelability, On sets polynomially enumerable by iteration, Exponential-time and subexponential-time sets, One-way functions and the isomorphism conjecture, On resource-bounded instance complexity, DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization, Collapsing degrees via strong computation, One-way functions and the nonisomorphism of NP-complete sets, A survey of one-way functions in complexity theory

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