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?

  • 3
    $\begingroup$ 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)$". $\endgroup$
    – Pål GD
    Feb 15, 2013 at 14:05

1 Answer 1


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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.