Algorithme randomisé pour 3SAT

Question

Il existe un algorithme randomisé très simple qui, étant donné un 3SAT, produit une affectation satisfaisant au moins 7/8 des clauses (dans l'attente): choisissez une affectation aléatoire. Une affectation aléatoire satisfait à chaque clause avec la probabilité 7/8, et donc la linéarité des attentes montre que la fraction attendue des clauses satisfaite par une affectation aléatoire est de 7/8.

Cela peut-il être fait de manière déterministe? Si oui, pourquoi sommes-nous intéressés par l'algorithme randomisé?