# How do I explain that a polynomial time reduction is in fact polynomial time?

I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete.

My solution is as follows, which is pretty much copied almost 100% from a textbook example with only an extra requirement for satisfiablity at the end...

$$QuadSat\leq_{p} Clique$$ Let $\phi$ be a formula with k clauses such as $$\phi=\bigwedge_{1}^{k}(a_k\vee b_k\vee c_k)$$ The reduction $f$ generates the strong $\langle G,k\rangle$, where $G$ is an undirected graph defined as follows:

The nodes in $G$ are organized into $k$ groups of three nodes each called the \textbf{triples}, $t_1, \dots, t_k$. Each triple corresponds to one of the clauses in $\phi$, and each node in a triple corresponds to a literal in the associated clause. Label each node of $G$ with its corresponding literal in $\phi$.

The edges of $G$ connect all but two types of pairs of nodes in $G$: No edge is present between nodes in the same triple, and no edge is present between two nodes with contradictory labels. $QuadSat$ is satisfiable if and only if the resulting graph $G$ contains four or more $k$-$cliques$. Each unique $k$-$clique$ in $G$ represents a set of satisfying assignments to $QuadSat$.

The reduction runs in polynomial time, because the construction of the graph is a polynomial function; one pass through all the triples to create all the vertices for $V$, and one pass through the same triples to create the edges.

I feel like my explanation as to why my reduction is polynomial in time is severely weak, possibly bordering on wrong. How can I explain this better?

And something else: I think this only proves that QuadSat is in NP, but not necessarily NP Complete. How can I prove this?

• The key is here: "the construction of the graph is a polynomial function; one pass through all the triples to create all the vertices ...". I think your problem is that you are hiding to much in the "polynomial time". It would be simpler to state the exact running time. We use $n^3$ to construct vertices, then $(n^3)^2 = n^6$ time to construct edges, or whatever. Then you finish with "that's all the steps, hence $O(n^6)$". Feb 15, 2013 at 14:05

Your reduction indeed shows that $QuadSAT\in NP$, since you showed a reduction to a problem in NP. Perhaps an easier way to have done this, is to simply show that there is a "short witness" for the membership of a formula in $QuadSAT$. In order to show NP-hardness, you must show a reduction from an NP-hard problem. A good candidate for that is $SAT$ (or $3SAT$).