# $L_2$ = {a,k | is a 3DNF (disjunctive normal form) and exist z such that safifies exactly k clauses in a} Validity of reduction $VC \leq_p L_2$ 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. Posted on Categories proxies