I have the following question :

$ L_2$ = {$ a,k$ | $ a$ is a 3DNF (disjunctive normal form) and exist $ z$ such that satisfies exactly $ k$ clauses in $ a$ }

I know that $ L_2 \in NPC$ .

Show that $ L_2 \in NP$ is relatively easy, I’ll skip that part.

I try to show that $ L_2 \in NPC$ using a reduction from $ VC \leq_p L_2$ (VC is vertex cover which we know in its $ NPC$ )

I defined the following function $ f$ :

$ $ f(G,k)=(a,k)$ $

I thought of something like that for each node $ i$ in $ G$ will define a literal $ x_i$ , and make it in $ 3DNF$ format, $ a=\bigvee(x_i \wedge x_i \wedge x_i)$ where $ 1 \leq i \leq n$ where $ n$ is the number of nodes in $ G$ . We can define that following $ z$ such that $ z$ safifies exactly $ k$ clauses, just give $ ‘1’$ literal $ x_i$ such that the node $ i$ is in the VC, and $ ‘0’$ otherwise, so such $ z$ exists.

So easy to see that $ (G,k) \in VC \implies (a,k) \in L_2$ since we showed explicitly such $ z$ that safifies exactly $ k$ clauses.

But I’m not sure the other side holds $ (G,k) \not\in VC \implies (a,k)\not\in L_2$ we given a graph that doesn’t have VC in size $ k$ but I think due to my building of a ($ a=\bigvee(x_i \wedge x_i \wedge x_i)$ ) we can find $ z$ that safifies exactly $ k$ clauses (actually we can find $ z$ that safifies $ x$ clauses where $ 1 \leq x \leq n$ where $ n$ is number of nodes in G.

So my reduction doesn’t hold?

Thanks.