Laboratory of Mathematical Logic at PDMI

Пятница, 17 ноября, комната 106. Начало в 16:00.

Докладчик: C. Николенко.

Тема: Как из задачи, NP-полной в наихудшем случае, сделать NP-полную в среднем.

Abstract

Доклад по статье Noam Livne ``All Natural NPC Problems Have Average-Case Complete Versions'' (ECCC TR06-122).

В статье изложена очень простая и понятная конструкция, которая трансформирует практически любую известную NP-полную задачу в задачу, полную в среднем. Это достигается за счёт того, что сначала полную в среднем задачу сводят к NP-полной обычным путём, а потом модифицируют NP-полную задачу так, чтобы это сведение ещё и сохраняло вероятностную меру.