Le langauge suivant $ P $ ou NPC $

Question

En supposant $ P \ NEQ NP $ est le suivant langauge $ P $ ou NPC $:
$ L = \ {\ langle \ phi \ rangle \ mid \ phi $ est une formule 3CNF avec une affectation satisfaisant au moins la moitié des clauses $ \} $

La première chose que j'ai essayé de le faire est de trouver une formule 3CNF $ \ phi $ tel que $ \ phi \ L Notin $ et je ne l'ai pas réussi à le faire. Est-il possible que tout simplement toutes les formules 3CNF ont une telle cession (et donc le problème est en $ P $) ou suis-je manque quelque chose?

Answer 1

Astuce: Prenez un $ d'évaluation v $ satisfaire moins de la moitié des clauses. Qu'en est-$ \ bar {v} $ l'évaluation telle que $ \ bar {v} (x) = \ neg v (x) $?