## Proceedings of the Seventh Annual Structure in Complexity Theory Conference: June 22-25, 1992, Boston University, Boston, MassachusettsProceedings of the conference held in Boston, Massachusetts, June 1992. No index. Annotation copyrighted by Book News, Inc., Portland, OR |

### What people are saying - Write a review

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

### Contents

Perceptrons PP and the Polynomial Hierarchy | 14 |

A Sublinear Space Polynomial Time Algorithm for Directed st Connectivity | 27 |

Some Properties of Exponential Time Complexity Classes | 50 |

Copyright | |

15 other sections not shown

### Common terms and phrases

accepts algebra algorithm automorphism binary boolean circuit boolean function communication complexity complexity classes Complexity Theory constant construct Corollary counting problem decision problems decision trees define definition denote depth deterministic evaluation exists EXPTIME finite structures fixed fixed-parameter tractability fixpoint logic formula func G SAT GapP graph G Hemachandra hierarchy IEEE input integer interactive proof systems IP(public isomorphism iterative Journal on Computing Kolmogorov complexity language Lemma length linear log-space LOGCFL lower bounds matrix monotone node nomial nondeterministic Note NP-complete obtain output P/poly Parameter path plexity poly poly-log polynomial polynomial hierarchy polynomial-time computable prob probabilistic probability Proc properties Proposition protocol prove pseudorandom PSPACE query network random oracle recursion reductions restricted result satisfies sequence space sparse sets stcon string Structure in Complexity subset threshold circuits threshold gate tion truth-table reducible Turing machine uniform variables vector vertex vertices weight