Skip to main content

# Unanswered Questions

10,472 questions with no upvoted or accepted answers
39 votes
1 answer
766 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 $s$-$t$ path $P$ ...
38 votes
1 answer
2k 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 ...
31 votes
1 answer
841 views

### Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
25 votes
1 answer
1k 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 ...
24 votes
1 answer
750 views

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 \... 23 votes 0 answers 1k views ### Can a calculus have incremental copying and closed scopes? A few days ago, I proposed the Abstract Calculus, a minimal untyped language that is very similar to the Lambda Calculus, except for the main difference that substitutions are ... 20 votes 1 answer 2k 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 ... 19 votes 1 answer 512 views ### Is finding a weight-balanced tree NP-hard? In the following, we consider binary trees where only the leaves have weights. Let$T$be a binary tree and$W(T)$be the sum of the weights of its leaves. Let$T.l$and$T.r$be the left child and ... 19 votes 1 answer 1k views ### Why hasn't functional programming researched dynamic trees? Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ... 18 votes 0 answers 323 views ### Using logic to prove non-regularity of a language A language$L$is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ... 17 votes 0 answers 378 views ### Is the two-color leapfrog problem in P? My question is whether a specific decision problem is in P or not. It's straightforwardly in NP. The decision problem is a specific case of the general$k$-color leapfrog problem. I can already show ... 17 votes 3 answers 897 views ### Steps that guarantee exiting a maze Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ... 15 votes 0 answers 716 views ### Test whether two languages are equal, when give in algebraic form This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages$L_1,L_2$that are expressed in "algebraic" form, as formalized below. I want to ... 14 votes 0 answers 247 views ### What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions? In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ... 14 votes 0 answers 2k views ### Barendregt's Variable Convention: what does it mean? Barendregt's Variable Convention: If$M_1,...,M_n\$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free ...

15 30 50 per page