How can an easy counting problem turn into an extremely hard one?
(well, quite easily...)
In the first half of this lecture, we give an overview about the most important complexity classes in computational complexity theory. In the second half of the lecture, a surprising new non-approximability result is presented.
It is well known that counting the solutions of the classic
binary tree coloring problem, the so-called small parsimony problem can be
done in polynomial running time. We prove that a small alteration is
sufficient to get a counting problem that is #P-complete, and cannot be
approximated even in a stochastic way unless RP = NP.
Joint work with Sandor Kiss.