Санкт - Петербургское отделение Математического института им. В.А. Стеклова РАН

ПРЕПРИНТ 10/2009

ВЕРХНЯЯ ОЦЕНКА ДЛЯ ЗАДАЧИ CIRCUIT SAT

This preprint was accepted December 1, 2009

АННОТАЦИЯ:
В данной работе приводится алгоритм для решения задачи Circuit SAT, 
время работы которого составляет O(2^{0.4058m}), где 
m -- количество гейтов во входной схеме. 

Ключевые слова: Circuit SAT,  слабо экспоненциальные алгоритмы 

  S.Nurk.  AN O(2^{0.4058m})  UPPER BOUND FOR CIRCUIT SAT

We present an algorithm for the Circuit SAT problem running in time
 $O(2^{0.4058m})$, where $m$ is the number of gates of the input circuit.

 Key words: Circuit SAT, weakly exponential algorithms


[Full text:
Preprint in Russian (.pdf.gz)
Preprint in English (.pdf.gz)]



Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg