The boolean hierarchy: Hardware over NP

This publication has 18 references indexed in Scilit:

• On sparse oracles separating feasible complexity classes
  Published by Springer Nature ,1986
• Computation times of NP sets of different densities
  Theoretical Computer Science, 1984
• Relativized polynomial hierarchies extending two levels
  Theory of Computing Systems, 1984
• Sparse sets in NP-P
  Published by Association for Computing Machinery (ACM) ,1983
• On the unique satisfiability problem
  Information and Control, 1982
• Parity, circuits, and the polynomial-time hierarchy
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1981
• 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
• Some connections between nonuniform and uniform complexity classes
  Published by Association for Computing Machinery (ACM) ,1980
• A second step toward the polynomial hierarchy
  Theoretical Computer Science, 1979
• The complexity of theorem-proving procedures
  Published by Association for Computing Machinery (ACM) ,1971