A note on sparse sets and the polynomial-time hierarchy

DOI10.1016/0020-0190(89)90193-2zbMath0688.68029OpenAlexW2080348906MaRDI QIDQ1263964

Shouwen Tang, Ronald V. Book

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90193-2

zbMATH Keywords

relativizationspolynomial time hierarchysparse oracle sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

A refinement of the low and high hierarchies ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

Cites Work

• Unnamed Item
• A low and a high hierarchy within NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Quantitative Relativizations of Complexity Classes
• Sparse Sets, Lowness and Highness

This page was built for publication: A note on sparse sets and the polynomial-time hierarchy