Proceedings of the Seventh Annual Structure in Complexity Theory Conference: June 22-25, 1992, Boston University, Boston, Massachusetts |
From inside the book
60 pages matching polynomial-time computable in this book
Where's the rest of this book?
Results 1-3 of 60
Contents
Perceptrons PP and the Polynomial Hierarchy | 14 |
The Power of Negative Thinking in Constructing Threshold Circuits for Addition | 20 |
A Sublinear Space Polynomial Time Algorithm for Directed st Connectivity | 27 |
Copyright | |
30 other sections not shown
Common terms and phrases
accepts algebra algorithm binary boolean boolean circuit complexity classes Complexity Theory computational complexity constant Corollary counting problem define definition denote depth deterministic equivalence exists EXPTIME finite structures first-order first-order logic fixed-parameter tractability fixpoint logic formula func function f graph G hard Hemachandra hierarchy IEEE input instance integer interactive proof systems isomorphism iterative Journal on Computing Kolmogorov complexity language Lemma length linear log-space lower bounds matrix NC¹ node nomial nondeterministic NP-complete NP-hard O(log obtained operator output P/poly path plexity polylog polynomial hierarchy polynomial-time computable predicate Proc properties Proposition prove pseudorandom PSPACE random oracle recursion reducible relational complexity relational machines relativized restricted satisfying sequence SIAM Journal space sparse sets STCON string subset Theorem threshold circuits threshold gate tion tree truth-table reducible Turing machine uniform universal relation variables vertex vertices weight