ProceedingsComputer Society Press of the IEEE, 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 algebra algorithm binary boolean boolean circuit boolean function communication complexity complexity classes Complexity Theory constant Corollary counting problem D₁ decision problems decision trees define definition denote depth deterministic exists EXPTIME finite structures first-order fixpoint logic formula func function f graph hard hash Hemachandra hierarchy IEEE input instance complexity integer interactive proof systems IP(public iterative Journal on Computing Kolmogorov complexity language Lemma length linear log-random-bits log-space LOGCFL lower bounds matrix NCą node nomial nondeterministic NP-complete NP-hard NP-hard set O(log output P/poly path plexity poly-tree-size polynomial polynomial hierarchy polynomial-time computable predicate probability Proc properties Proposition protocol prove pseudorandom PSPACE queries random oracle recursion reductions relativized restriction satisfies sequence SIAM Journal space sparse sets string subset Theorem tion truth-table reducible Turing machine universal relation variables vector Verifier vertex vertices