Structure of complexity classes: Separations, collapses, and completeness

This publication has 40 references indexed in Scilit:

• Enumerative counting is hard
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1988
• Generic oracles and oracle classes
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1987
• A note on complete problems for complexity classes
  Information Processing Letters, 1986
• Three results on the polynomial isomorphism of complete sets
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1986
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
  Published by Association for Computing Machinery (ACM) ,1986
• The boolean hierarchy: Hardware over NP
  Published by Springer Nature ,1986
• The complexity of sparse sets in P
  Published by Springer Nature ,1986
• Parity, circuits, and the polynomial-time hierarchy
  Theory of Computing Systems, 1984
• On Isomorphisms and Density of $NP$ and Other Complete Sets
  SIAM Journal on Computing, 1977
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
  SIAM Journal on Computing, 1975