Non-uniform proof systems: A new framework to describe non-uniform and probabilistic complexity classes
Author:
- 1 January 1988
- book chapter
- Published by Springer Nature
- p. 193-210
Abstract
No abstract availableKeywords
This publication has 26 references indexed in Scilit:
- On hiding information from an oracle1987
- On helping by robust oracle machinesTheoretical Computer Science, 1987
- Sparse Sets, Lowness and HighnessSIAM Journal on Computing, 1986
- On Circuit-Size Complexity and the Low Hierarchy in NPSIAM Journal on Computing, 1985
- Trading group theory for randomness1985
- On self-reducibility and weak P-selectivityJournal of Computer and System Sciences, 1983
- Some observations on the probabilistic algorithms and NP-hard problemsInformation Processing Letters, 1982
- AlternationJournal of the ACM, 1981
- Some connections between nonuniform and uniform complexity classes1980
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977