ProceedingsSpringer-Verlag, 1992 - Computational complexity |
Contents
Majority Gates vs General Weighted Threshold Gates | 2 |
Perceptrons PP and the Polynomial Hierarchy | 14 |
The Power of Negative Thinking in Constructing Threshold Circuits for Addition | 20 |
Copyright | |
30 other sections not shown
Other editions - View all
Common terms and phrases
accepts algorithm assume binary boolean bound called characterization circuit closed complexity classes Complexity Theory Computer Science consider constant construct contains Corollary corresponding counting cover define definition denote depth deterministic easy elements equivalence evaluation example exists expression extensible fact finite fixed fixpoint logic formula function gates give given graph hard Hence hierarchy holds IEEE input instance integer iterative Journal known language least Lemma length lower bounds natural node nondeterministic Note obtained operator oracle output path polynomial polynomial-time positive probability problem Proceedings proof properties Proposition prove queries question random reducible relation respectively restricted result satisfying sequence solution space sparse sparse sets step string structures Theorem threshold tion tree Turing machine uniform universal variables vertex vertices weight witnessing