$$QuadSatleq_{p} Clique$$ Let $phi$ be a formula with k clauses such as $$phi=bigwedge_{1}^{k}(a_kvee b_kvee c_k)$$ The reduction $f$ generates the strong $langle G,krangle$, 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?
Asked By : agent154
Answered By : Shaull
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9806 3.2K people like this
