Miklós István

Rényi Intézet

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.