| ##2 1 (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We present a randomized DNA algorithm for k-SAT based on the classical algorithm of Paturi et al. [8]. For an n-variable, m-clause instance of k-SAT (m> n), our algorithm finds a satisfying assignment, assuming one exists, with probability 1-e- # , in worst-case time O(k 2 mn) and space O(2 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||