What people are saying - Write a review
We haven't found any reviews in the usual places.
On Tally Relativizations of BPComplexity Classes Preliminary Report
Decision Trees and Downward Closures Extended Abstract
On Uniformity within NC
19 other sections not shown
Other editions - View all
1-reversal algorithm alternating Turing machines automaton binary bits Boolean circuit Boolean formula Boolean hierarchy bounding functions circuits class of languages closed under complementation co-NP complete sets complexity classes complexity theory Computer Science configuration conjecture construction context-free languages Corollary defined definition denote deterministic encoding equivalent exists fan-in finite function game automata Godel numberings Hartmanis Hemachandra IEEE implies induction infinite input integer interactive proof systems isomorphism Juris Hartmanis Kolmogorov complexity languages accepted Lemma logspace lower bound nodes nomial nondeterministic notion NP oracle NP-complete oracle machine paper path player plexity poly polynomial complexity core polynomial-time hierarchy probabilistic Proc proper polynomial complexity prove PSPACE quantifiers queries random recursive set relativized Schoning self-reducibility sequence simulate space bounded sparse oracle sparse set strategy strings of length subset symbol tally set tape Theory of Computing tion truth-table reducibility Turing machine