Cheap and Secure Web Hosting Provider : See Now

[Solved]: How must Grovers algorithm be modified in order to solve 3-SAT?

, , No Comments
Problem Detail: 

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?

Asked By : vauge

Answered By : D.W.

Grover's algorithm is already suitable. It promises that if there is at least one match, then it will output at least one match. It doesn't promise to output all matches, but you don't need all matches.

It is usually described to work in the case where there is zero or one items that match, but that's just because those are the hardest cases. If there are multiple matches, the algorithm will still work and will still find a match; and the running time will remain the same.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback