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 ...