## Proceedings, Volume 15, Part 2000 |

### What people are saying - Write a review

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

### Contents

TUTORIAL | 2 |

A Lower Bound for the Shortest Path Problem | 14 |

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

Copyright | |

26 other sections not shown

### Other editions - View all

### Common terms and phrases

3-colorable accepts algebraic algorithm Alice and Bob assume bits Boolean circuit Boolean function cell chain clause-sets clauses colors combinatorial complexity classes Computational Complexity Computer Science concept class conﬁguration consider constant construct Corollary deﬁned Deﬁnition denote depth deterministic edge elements encoding exists fan-in ﬁnd ﬁnite automata ﬁrst ﬁxed fonnula Fortnow function f gates given graph Hence IEEE implies induction inequality input K-dimension Kolmogorov complexity language LBSP Lemma length linear LOGCFL logspace lower bounds many-one reductions matrix node nondeterministic Note NP-complete NP-hard O(log optimal output path PCP theorem plexity polynomial polytime preﬁx function probabilistic problem proof of Theorem prove PSPACE quantiﬁer quantum qubit query query complexity random reduction result satisﬁability simulation space step string subpolynomial subset sufﬁces sufﬁciently tape tensor formula Theory tion truth table Turing machine upper bound variables vector vertices