Proceedings, Eleventh Annual IEEE Conference on Computational Complexity: May 24-27, 1996, Philadelphia, PennsylvaniaJin-yi Cai, Steve Homer |
Contents
Nondeterministic NC Computation | 12 |
Session 2 | 23 |
Collapsing OracleTape Hierarchies | 33 |
Copyright | |
26 other sections not shown
Other editions - View all
Common terms and phrases
accepts algorithm answer approximating assignment assume bits block Boolean bounded called circuit Claim closed collapses complexity complexity classes Computer Science condition consider constant construction contains corresponding define definition denote depth deterministic distribution edge encoding equivalent error example exists fact finite fixed formula function function f gate give given graph hard hence hierarchy holds IEEE implies independent input integer known language least Lemma length logspace maps measure min-entropy node Note notion NPMV O(log obtained oracle output partial path pebble polynomial polynomial-time positive possible probability problem Proc proof properties Proposition prove queries question random reductions satisfying sequence simulation solution space sparse step string Structure subset tape Theorem Theory tion Turing machine uniform University variables vertex vertices