1997 12th Annual IEEE Conference on Computational Complexity
What people are saying - Write a review
We haven't found any reviews in the usual places.
Inequalities for Shannon Entropies and Kolmogorov Complexities
Circuits Over PP and PL
The General Notion of a DotOperator
25 other sections not shown
Alice and Bob alternating Turing machine approximation assignment assume Beigel binary bits Boolean circuits Boolean function bottom fan-in checker clauses complexity classes complexity theory consider constant constraint Corollary database datalog defined Definition denote depth deterministic distribution dot-operators elements equivalent exists exponential fan-in finite gates given graph Group Intersection groupoid hierarchy IEEE implies inequality input instance integer Johnson's Algorithm Kolmogorov complexities language leaf Lemma length linear logic programming logspace lower bound mapping Max-Sat mixed strategy MlN WEIGHT MODm NEXPTIME node nondeterministic Note NP-complete obtain online algorithms oracle output perceptron permutation player polyabelian polynomial hierarchy polynomial-time Proc proof of Theorem protocol prove PSPACE queries random reducibility resp satisfied Section sequence simulation solvable space strategy string subset Symposium Theoretical Computer Science tion Turing machine uniform upper bound variables vector