Questions tagged [speed-up]
The speed-up tag has no usage guidance.
4
questions
11
votes
1
answer
669
views
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 ...
- 244
6
votes
1
answer
254
views
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 (...
- 13.9k
9
votes
2
answers
260
views
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 ...
- 21.5k
14
votes
3
answers
577
views
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 \...
- 21.5k