Home

Семинар 26 мая 2006 года

Пятница, 26 мая, комната 106. Начало в 17:30.

Докладчик: С. Федин.

Тема: Unique k-SAT is as Hard as k-SAT.

Abstract

Доклад по статье Subhas Kumar Ghosh ``Unique k-SAT is as hard as k-SAT''

In this work we show that Unique k-SAT is as hard to solve as general k-SAT for every natural k, where k-SAT denotes the satisfiability problem for k-CNFs and Unique-k-SAT is a promise version where the given formula has 0 or 1 solutions.

Namely, defining $ s_k $ as the infimum of d such that there exists a $ O(2^{d n}) $-time randomized algorithm for k-SAT, and defining similary $ g_k $ for randomized algorithms for Unique-k-SAT, we show that for every k $ s_k = g_k $.