ProceedingsSpringer-Verlag, 1988 - Computational complexity |
Contents
On Tally Relativizations of BPComplexity Classes Preliminary Report | 10 |
Decision Trees and Downward Closures Extended Abstract | 29 |
On Uniformity within NC | 47 |
Copyright | |
19 other sections not shown
Other editions - View all
Common terms and phrases
accepted algorithm alternating answer applies assume automata bits Boolean bounded called characterization circuits closed collapses complementation complexity complexity classes complexity core computation Computer Science condition configuration consider construction contains Corollary counting defined definition denote deterministic equal equivalent example exists fact finite fixed formula function gates give given hard Hartmanis Hence hierarchy implies infinite input isomorphism Kolmogorov complexity languages Lemma length logspace natural nondeterministic Note notion obtained oracle pair path player polynomial prediction probabilistic probability problems Proc proof proper properties prove quantifiers queries question random recursive reducibility requires respect satisfying sequence simulate space sparse set step strategy strings structure symbol tally set tape Theorem Theory tion tree true Turing machine uniform University