Circuit depth relative to a random oracle
type: Item
instance of: scholarly article
title: Circuit depth relative to a random oracle
zbMATH Open document ID: 0779.68035
DOI: 10.1016/0020-0190(92)90225-K
author: Peter Bro Miltersen
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: The study of separation of complexity classes with respect to random oracles was initiated by \textit{H. C. Bennett} and \textit{J. Gill} [SIAM J. Comput. 10, 96-113 (1981; Zbl 0454.68030)] and continued by many researchers. Computation relative to an oracle \(A\), where \(A\subseteq \{0,1\}^*\) is a computation which is allowed to ask queries of the form \(y\in A\)? and get answers. A random oracle \(A\) is simply a random (with respect to Lebesgue measure) subset of \(\{0,1\}^*\), i.e. for each \(x\in \{0,1\}^*\), \(x\in A\) with probability \(1/2\) and all these events are mutually independent. \textit{C. B. Wilson} [Math. Syst. Theory 20, 13-29 (1987; Zbl 0627.68043); SIAM J. Comput. 19, No. 2, 384-396 (1990; Zbl 0692.68045)] defined relativized circuit depth and constructed various oracles \(A\) for which \(P^ A\neq NC^ A\), \(NC^ A_ k\neq NC^ A_{k+\epsilon}\), \(AC^ A_ k\neq AC^ A_{k+\epsilon}\), \(AC^ A_ k\not\subseteq NC^ A_{k+1-\epsilon}\) and \(NC^ A_ k\not\subseteq AC^ A_{k-\epsilon}\) for all positive rational \(k\) and \(\epsilon\), thus separating those classes for which no trivial argument shows inclusion (the definition of \(NC^ A_ k\) and \(AC^ A_ k\) is restricted to rational \(k\) for constructibility reasons). In this note we show that as a consequence of a single lemma, these separations (or improvements of them) hold with respect to a random oracle \(Q\) with probability 1.
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 92133
zbMATH Keywords: separation of complexity classes with respect to random oracles
zbMATH Keywords: relativized circuit depth
MaRDI profile type: Publication
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Constant Depth Reducibility
cites work: Circuit size relative to pseudorandom oracles
cites work: Relativized circuit complexity
cites work: RelativizedNC
cites work: On the Decomposability of $NC$ and $AC$
description: scientific article; zbMATH DE number 92133