> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-3/advanced_topics/computational_complexity/classic-npc-problems.md).

# Classic NPC Problems

## 3-SAT

Given a CNF formula $$\phi$$, is there a satisfying assignment?

instance $$s$$:

$$\phi = (\overline{x\_1} \lor x\_2 \lor x\_3) \land (x\_1 \lor \overline{x\_2} \lor x\_3) \land (\overline{x\_1} \lor x\_2 \lor x\_4)$$

certificate t:

$$x\_1 = true, x\_2 = true, x\_3 = false, x\_4 = false$$

## Set Cover Problem

Given a set $$U$$ of elements, a collection of subsets of $$U$$, $$S\_1, S\_2, S\_3, ..., S\_m$$, and an integer $$K$$, does there exist a collection of size $$\leq K$$ whose union is equal to $$U$$?

Example:

$$U = {1, 2, 3, 4, 5, 6, 7}$$

$$S\_1 = {3, 7}, S\_2 = {2, 4}, S\_3 = {3, 4, 5, 6}, S\_4 = {1}, S\_5 = {1, 2, 6, 7}$$

Let $$K = 2$$. Yes, we have $$S\_3$$ and $$S\_5$$.

## Vertex Cover Problem

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Finding a minimum vertex cover is NP-hard. The decision version is NP-complete. To formally state this,

given an undirected graph $$G = (V, E)$$, a vertex cover of $$G$$ is a subset $$V' \in V$$ such that, for every edge $$(u, v) \in E$$, we have either $$u \in V'$$ or $$v \in V'$$. Is there a vertex cover such that $$|V'| \leq K$$ ?

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-Ltpq_IdouPsgikXP9Jx%2FVC%20examples.jpg?generation=1573935273879772\&alt=media)

VC is a special case of set cover. Here is the reduction from vertex cover. So set cover is at least as hard as VC.

Let $$K = K, U = E, S\_v = {e \in E : e ; incident ; to ; v }$$, then set cover of size $$\leq K$$ iff vertex cover of size $$\leq K$$.

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-Ltpq_If7oDIVKUGawOt%2FScreen%20Shot%202016-12-09%20at%203.54.04%20PM.png?generation=1573935274121760\&alt=media)

## Clique Cover Problem

## Independent Set Problem

In a graph, an independent set is a set of vertices such that no two of which are adjacent. A maximum independent set is an independent set of largest possible size for a given graph G. Again, max independent set is NP-hard. The decision version of independent set is NPC.

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-Ltpq_IhTQmu4KqrLqCW%2Find%20set%20example.jpg?generation=1573935274227235\&alt=media)

## Reference

* [List of NPC Problems](https://en.wikipedia.org/wiki/List_of_NP-complete_problems)
* Proof [VC is NPC](http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2001/CW/npproof.html)