是$ p $或$ npc $的以下langauge

Question

假设$ p neq np $是$ p $或$ npc $的以下langauge：
$ l = { langle phi rangle mid phi $是一个3cnf公式，分配满足至少一半的条款$ } $

我尝试做的第一件事是找到一个3cnf公式$ phi $，这样$ phi notin l $，我尚未设法这样做。仅仅所有3CNF公式都可能具有这样的作业（因此问题是$ p $），还是我缺少一些东西？

Answer 1

提示：采取估值$ v $满足不到一半的条款。 $ bar {v} $的估值又如何呢？$ bar {v}（x）= neg v（x）$？