Questions tagged [speed-up]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
1 answer

Is Gödel's speed-up theorem an instance of Blum's speedup theorem?

Blum's speedup theorem is a statement about a certain class of computable functions for which it is always possible to find a program of lower complexity. Gödel's speed-up theorem is a statement about ...
Rexcirus's user avatar
  • 244
6 votes
1 answer

Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

This is another attempt to formalize my former question on the topic. I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
domotorp's user avatar
  • 13.9k
9 votes
2 answers

Is a quadratic nondeterminism speed-up of deterministic computation plausible?

This is a follow up to nondeterministic speed-up of deterministic computation. Is it plausible that nondeterminism (or more generally alternation) would allow a general quadratic speed-up of ...
Kaveh's user avatar
  • 21.5k
14 votes
3 answers

Nondeterministic speed-up of deterministic computation

Can nondeterminism speed-up deterministic computation? If yes, how much? By speeding-up deterministic computation by nondeterminism I mean results of the form: $\mathsf{DTime}(f(n)) \subseteq \...
Kaveh's user avatar
  • 21.5k