Computational Complexity: Proceedings : Fifteenth Annual IEEE Conference on Computational Complexity : July 4-7, 2000, Florence, Italy |
Contents
A Lower Bound for the Shortest Path Problem | 14 |
TimeSpace Lower Bounds for SAT on Uniform and NonUniform Machines | 22 |
BP f 0 L l+E | 36 |
Copyright | |
23 other sections not shown
Other editions - View all
Common terms and phrases
accepts addition algebraic algorithm apply arbitrary assume bits Boolean called circuit classical colors complexity computation Computer Science condition consider constant construct contains Corollary corresponding defined definition denote depth determine deterministic edges elements equal equivalent example exists fact finite fixed formula function gates give given graph hard Hence holds IEEE implies induction input integer known Kolmogorov language least Lemma length linear logspace lower bounds matrix multiplication natural node nondeterministic Note O(log obtain operations optimal output path polynomial positive possible probability problem proof prove quantum query random reduction respectively result running satisfiability similar simulation space step string takes tape tensor formula Theorem Theory tion tree Turing machine University variables vector vertices weight