New answers tagged co.combinatorics
1
A simple bound is that we could use a program generating $x$, a starting index $1 \leq i \leq n$ and length $m$ to get a program generating any choice of $v$, and thus $C(v)$ is bounded as
$$\forall v: k \leq C(v) \leq C(x) + \log(n) + \log(m) + c,$$
where $c$ is some constant overhead independent from $x,v$ that represents the steps necessary to take a ...
Top 50 recent answers are included
Related Tags
co.combinatorics × 608graph-theory × 242
ds.algorithms × 100
reference-request × 79
cc.complexity-theory × 70
graph-algorithms × 54
optimization × 28
boolean-functions × 27
pr.probability × 21
coding-theory × 20
expanders × 18
np-hardness × 17
approximation-algorithms × 17
permutations × 17
cg.comp-geom × 15
it.information-theory × 15
graph-colouring × 15
extremal-combinatorics × 15
fourier-analysis × 14
fl.formal-languages × 13
automata-theory × 13
spectral-graph-theory × 13
counting-complexity × 12
linear-programming × 11
terminology × 11