Relativized circuit complexity
- 31 October 1985
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 31 (2) , 169-181
- https://doi.org/10.1016/0022-0000(85)90040-6
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- On Relativizations of the P =? NP Question for Several StructuresElectronic Notes in Theoretical Computer Science, 2008
- On relativized exponential and probabilistic complexity classesInformation and Control, 1986
- Relativized polynomial hierarchies extending two levelsTheory of Computing Systems, 1984
- A Boolean function requiring 3n network sizeTheoretical Computer Science, 1983
- BPP and the polynomial hierarchyInformation Processing Letters, 1983
- A complexity theoretic approach to randomnessPublished by Association for Computing Machinery (ACM) ,1983
- Relativized Questions Involving Probabilistic AlgorithmsJournal of the ACM, 1982
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean FunctionsSIAM Journal on Computing, 1977
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975