Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
 Что: Лекция Когда: Среда, 12 марта 2014, 18:00–19:35 Где: ПОМИ РАН

#### Описание

We discuss (a bit unusual) behavior of certain NP-complete problems admitting subexponential algorithms. For example, the $$p$$-Clustering problem is to decide for a given $$n$$-vertex graph $$G$$ and integers $$k$$ and $$p$$, if $$G$$ can be turned into a $$p$$-cluster (disjoint union of $$p$$ cliques) by at most $$k$$ edge modifications (adding/deleteling edges). We give a subexponential algorithm solving this problem in time $$O(exp((\sqrt{qp}) +n +m)$$. On the other hand, there are strong arguments showing that most of NP-complete problems cannot be solved in subexponential time. While existence of subexponential time algorithms does not resolve P vs NP question, it shows an interesting diversity of the world of intractable problems.