1997 12th Annual IEEE Conference on Computational Complexity |
Contents
Inequalities for Shannon Entropies and Kolmogorov Complexities | 13 |
Circuits Over PP and | 24 |
The General Notion of a DotOperator | 36 |
Copyright | |
25 other sections not shown
Other editions - View all
Common terms and phrases
accepting algorithm Alice approximation assignment assume bits Boolean bottom called circuit classes clauses closed complexity Computer Science consider constant constraint construct contains Corollary corresponding defined Definition denote depth distribution easy element equal equivalent example exists expressed extension fact fan-in finite fixed function gates give given graph hard Hence hierarchy holds IEEE implies inequality input instance known language least Lemma length linear lower bound mapping MODm monotone node Note obtain operator oracle output permutation polynomial polynomial-time positive possible probability problem proof protocol prove queries question random reducibility relation require respectively restriction result satisfied separation simulated solvable space step string structure Suppose System Theorem Theory tion tree true Turing machine uniform University variables WEIGHT