Évaluation de l'algorithme de Grover sur 3-SAT
-
02-11-2019 - |
Question
J'ai récemment demandé cette Question très similaire sur la façon dont l'algorithme des groovers doit être modifié afin de résoudre 3-SAT et a appris qu'il n'a pas besoin de modification.
Cependant, ce que je n'obtiens toujours pas, c'est comment déterminer si une affectation variable satisfaisante a été trouvée après avoir appliqué l'algorithme de Grover. La dernière étape (comme décrit dans Wikipédia) est de mesurer $ λ_ω $ qui, dans le cas de la résolution de 3-SAT, me donnerait une affectation pour les variables de ma formule. Dois-je vérifier manuellement si cette affectation est effectivement une affectation satisfaisante? Ou y a-t-il un meilleur moyen de savoir s'il existe au moins un match?
Pas de solution correcte