1996 11th Annual IEEE Conference on Computational Complexity
What people are saying - Write a review
We haven't found any reviews in the usual places.
Nondeterministic NC1 Computation
Parallel Complexity Hierarchies Based on PRAMs
Collapsing OracleTape Hierarchies
24 other sections not shown
accepts algorithm approximating automorphism binary Boolean boolean circuit branching programs collapses complexity classes Complexity Theory Computer Science coNPMV constant construction Corollary define definition denote deterministic Dlogtime-uniform dyadic rational edge encoding exists extractors fan-in finite formula free vertex func gate hence IEEE implies independent set input bits integer program isomorphism L-printable Lemma logspace lower bound many-one many-one reductions maps min-entropy multivalued functions node nonadaptive nondeterministic Note notion NP-complete NPMV NPSV oracle tape oracle Turing machine output bit p-measure p-selective partial multivalued functions pebble polynomial hierarchy polynomial-time computable Pp-COmp probabilistic problem Proc proof system properties Proposition prove PSPACE queries random bits real number recursive satisfying assignment Selman sequence simulation solution space space-bounded strings of length subgraph subset Symposium test tube Theorem Theory of Computing tion truth-table reducible Turing machine uniform variables VC dimension vertex vertices width