Questions tagged [complexity-theory]
The complexity-theory tag has no usage guidance.
5
questions with no upvoted or accepted answers
6
votes
0
answers
214
views
Small universal monotone Turing machines
This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
1
vote
0
answers
124
views
Bounds on the construction of regular expressions' intersection operator
There are references on the exponential worst-case of the intersection operator for regular expressions (see [1]). However, I was wondering if there are similar results for the construction process ...
1
vote
0
answers
179
views
Network Reliability Problem
Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
0
votes
0
answers
41
views
Unbounded Knapsack: Does Increasing capacity increase optimal value?
Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
0
votes
0
answers
72
views
Number of outputs produced by levin search variant (SIMPLE)
Let $f$ be an inverting problem. If there is an algorithm A that invert $f$ in time $t(n)$, then the SIMPLE algorithm below invert $f$ in time $c.t(n)$ where $c$ is a constant depending only on $A$
...