## Proceedings of the ... Annual Structure in Complexity Theory Conference, Volume 7 |

### What people are saying - Write a review

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

### Contents

Perceptions 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

### Other editions - View all

### 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 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 polynomial polynomial hierarchy polynomial-time computable predicate 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 Verifier vertex vertices weight