The Boolean Hierarchy I: Structural Properties

This publication has 14 references indexed in Scilit:

• On complete problems for NP∩CoNP
  Published by Springer Nature ,2005
• The Boolean Hierarchy II: Applications
  SIAM Journal on Computing, 1989
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
  SIAM Journal on Computing, 1988
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
  SIAM Journal on Computing, 1987
• Complexity classes without machines: On complete languages for UP
  Published by Springer Nature ,1986
• The boolean hierarchy: Hardware over NP
  Published by Springer Nature ,1986
• On sparse oracles separating feasible complexity classes
  Published by Springer Nature ,1986
• Relativized polynomial hierarchies extending two levels
  Theory of Computing Systems, 1984
• On the unique satisfiability problem
  Information and Control, 1982
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
  SIAM Journal on Computing, 1981