Downward translations of equality

DOI10.1016/0304-3975(90)90099-4zbMath0701.68027OpenAlexW2080042331MaRDI QIDQ914368

N. E. Zubov

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0304-3975(90)90099-4

zbMATH Keywords

relativizationoraclesequality of complexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A downward translation in the polynomial hierarchy, Limitations of the upward separation technique, A Downward Collapse within the Polynomial Hierarchy, Sparse sets and collapse of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some results on relativized deterministic and nondeterministic time hierarchies
• Complexity of Presburger arithmetic with fixed quantifier dimension
• On-line simulation of k + 1 tapes by k tapes requires nonlinear time
• Sparse Sets in : Relativizations
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Oracle‐Constructions to Prove All Possible Relationships Between Relativizations of P, NP, EL, NEL, EP and NEP
• Limitations on Separating Nondeterministic Complexity Classes
• Relativizing Time, Space, and Time-Space
• Tally languages and complexity classes