692 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
1k views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let $\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ... 1answer 840 views Is Logical Min-Cut NP-Complete? Logical Min Cut (LMC) problem definition Suppose that$G = (V, E)$is an unweighted digraph,$s$and$t$are two vertices of$V$, and$t$is reachable from$s$. The LMC Problem studies how we can ... 0answers 204 views Finding an st-path in a planar graph which is adjacent to the fewest number of faces I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph G, and two vertices s and t, find an st-path$P$which minimizes ... 0answers 384 views on “On the cruelty of really teaching computing science” Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course: On the one hand, we teach what looks like the ... 0answers 312 views Approximate minimum-weighted tree decomposition on complete graphs Say I have a weighted undirected complete graph$G = (V, E)$. Each edge$e = (u, v, w)$is assigned with a positive weight$w$. I want to calculate the minimum-weighted$(d, h)$-tree-decomposition. By ... 0answers 300 views Graph problem known to be$NP$-complete only under Cook reduction The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ... 0answers 270 views Solving divide & conquer reccurences if the split-ratio depends on$n$Is there a general method to solve the recurrence of the form:$T(n) = T(n-n^c) + T(n^c) + f(n)$for$c < 1$, or more generally$T(n) = T(n-g(n)) + T(r(n)) + f(n)$where$g(n),r(n)$are some ... 1answer 381 views Could min cut be easier than network flow? Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a$(s,t)$-min-cut. Therefore, the complexity of computing a ... 1answer 458 views Compression of domain names I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ... 0answers 124 views Machines for context-free languages which gain no extra power from nondeterminism When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ... 0answers 177 views Is there an O(n log n) algorithm for 4D line simplification? The Ramer-Douglas-Peucker algorithm for line simplification has worst-case$O(n^2)$runtime. For suitably distributed random inputs, it has expected$O(n \log n)$runtime complexity. In 2D, there are ... 0answers 329 views Complexity of deciding whether there is a winning strategy in the following game The sum divider game for$n$starts with the set$M_0 = \{1,\dots,n\}$. Player A chooses a number$m_1$from$M_0 \setminus \{1\}$and B has to choose a divider$m_2$of$m_1$from$M_1 = M_0 \...
Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...