15th Annual IEEE Conference on Computational Complexity
What people are saying - Write a review
We haven't found any reviews in the usual places.
A Lower Bound for the Shortest Path Problem
TimeSpace Lower Bounds for SAT on Uniform and NonUniform Machines
24 other sections not shown
Other editions - View all
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