Questions tagged [speed-up]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
14
votes
3answers
490 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 \...
5
votes
1answer
225 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 (...