# How must Grovers algorithm be modified in order to solve 3-SAT?

Grover's algorithm was designed for a database with exactly one item that matches a given search criterion, and can be used to find that very item.

However, when checking whether a given formula is in 3-SAT, I don't know how many items match the search criterion (i.e. how many interpretations satisfy the formula) and I just want to know whether there is at least one. So, what steps have to be taken in order to make Grover's algorithm suitable for 3-SAT?

• @vzn On the contrary. If you are given an arbitrary list of length $n$, Grover's algorithm doesn't help you – you have to check all entries, and this takes linear time. The list (or database) has to be given implicitly through an oracle for the speedup (and the algorithm) to make sense. – Yuval Filmus Apr 21 '15 at 18:07
Notwithstanding D.W.'s answer, the other option, if all you knew about Grover's algorithm is that it requires unique solutions, is to use the work of Valiant and Vazirani. Without getting into details, the idea is like this. Suppose that there are roughly $2^k$ solutions. We add random constraints that "kill" a solution with probability $2^{-k}$. With constant probability, the resulting instance has a unique solution. While we don't know $k$, there are only polynomially many possible $k$s, so we can enumerate over all of them.