Skip to main content

Questions tagged [tradeoff]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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
1 vote
0 answers

Tradeoff between running time and depth in neural network

I might not be in the good stack-exchange site, so please forgive me. Let consider a neural network that we want to train to a certain task. For the purpose of my research, I am wiling to reduce the ...
Binou's user avatar
  • 171
1 vote
0 answers

Parametrically-relaxed Kolmogorov complexity

Consider the following problem: Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation. Output: The encoding of some kind of automaton (say, a Turing machine) which ...
einpoklum's user avatar
  • 173
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.7k
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