## Proceedings, Volume 12, Part 1997IEEE Computer Society Press - Computational complexity |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Inequalities for Shannon Entropies and Kolmogorov Complexities | 13 |

Circuits Over PP and PL | 24 |

The General Notion of a DotOperator | 36 |

Copyright | |

19 other sections not shown

### Other editions - View all

### Common terms and phrases

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 inequality input instance integer Johnson's Algorithm Kolmogorov complexities language leaf Lemma length linear logic programming lower bound mapping Max-Sat mixed strategy MlN WEIGHT MODm NEXPTIME node nondeterministic Note NP-complete obtain online algorithms optimal oracle output perceptron permutation player polyabelian polynomial polynomial hierarchy polynomial-time problem Proc proof of Theorem protocol prove PSPACE queries random reducibility resp satisfied Section sequence simulation solvable space strategy string subset Symposium tion Turing machine uniform upper bound variables vector