Circuit depth relative to a random oracle

DOI10.1016/0020-0190(92)90225-KzbMath0779.68035MaRDI QIDQ1198081

Peter Bro Miltersen

Publication date: 16 January 1993

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

zbMATH Keywords

relativized circuit depthseparation of complexity classes with respect to random oracles

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Relativized circuit complexity
• Circuit size relative to pseudorandom oracles
• On the Decomposability of $NC$ and $AC$
• Constant Depth Reducibility
• RelativizedNC
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

This page was built for publication: Circuit depth relative to a random oracle