Skip to main content

Questions tagged [tradeoff]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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.7k
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
  • 14k