Tag Archives: Markov chain

Two nasty counting problems

OK, let’s get started. Here are two nasty counting problems, my favorite ones. They look pretty easy but they are actually extremely hard. That’s why they are nasty.

The first one

Given k different colors, and from each color, there are n1n2 … nk number of balls with the given color (ni might be 0). Furthermore, there are k-1 gray balls, gray is not amongst the k colors. How many ways are there to order the balls into a sequence such that the number of gray balls in any prefix is at most the number of finished colors minus 1. A color is finished in a prefix if it does not appear in the corresponding suffix.

Prove of disprove that this counting problem is #P-complete.

There is a simple Markov chain which swaps two consecutive balls if the resulting sequence is also an allowed order. It is easy to show that this Markov chain is irreducible. Prove or disprove that this Markov chain is rapidly mixing. Note that rapid mixing would provide an FPRAS approximation as the counting problem is self-reducible.

Please, measure the size of the problem in unary. Namely, the size of the problem is the number of balls, and not the number of digits you need to describe the problem.

The second one

Prove or disprove that counting the most parsimonious DCJ scenarios  is #P-complete.

Why they are hard?

Good question. My opinion is that we have too little freedom here. To be able to prove #P-completeness, another #P-complete problem should be reduced to it, like the #2-SAT. However, a single series of numbers completely define the first counting problem. How to transform a 2-CNF into this colored balls problem? Unclear. Funnily, the suggested Markov chain is also nastily hard to prove to be rapidly mixing…

The other problem is at least known to be in FPRAS and FPAUS. But also has too little freedom. We have a formula to calculate the exact number of solutions, which is permanent-like. The problem with it is not that it is only permanent-like, but we have a very special matrix here: all the values are determined by the raws and columns, ie. the degree of freedom grows only linearly with the sum of the number of columns and rows. With other words, the degree of freedom is approximately the square root of the size of the entire matrix. Could such a simple problem already be #P-complete?

Another possible way to solve these problems is to prove that they can be solved in polynomial time. Good luck! Did I mention that they were nasty? I mean, they are really, really…