## 15th Annual IEEE Conference on Computational Complexity |

### What people are saying - Write a review

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

### Contents

A Lower Bound for the Shortest Path Problem | 14 |

TimeSpace Lower Bounds for SAT on Uniform and NonUniform Machines | 22 |

SESSION 2 | 35 |

Copyright | |

24 other sections not shown

### Other editions - View all

### Common terms and phrases

accepts algebraic algorithm Alice and Bob arbitrary assume automata binary bits Boolean circuits Boolean function branching program chain circuit classical clause-sets clauses colors complexity classes Computational Complexity Computer Science conjecture consider constant construct Corollary defined definition denote depth deterministic deterministic Turing machine edges elements encoding exists fan-in finite FOLL Fortnow gates given graph Hence IEEE implies induction inequality input integer Kolmogorov complexity LBSP Lemma length linear LOGCFL logn logspace lower bounds many-one reductions matrix node nondeterministic Note NP-complete O(logn obtain optimal output P/poly permutation plexity polynomial polytime probabilistic problem proof of Theorem prove QACC qubit query query complexity random read-once reduction result Section semiring Shortest Path problem simulation solvable groups space step string subformula subpolynomial subset tape tensor formula Theory tion Turing machine upper bound variables vector vertices weight