CS3230 - Chapter 10: NP Completeness

Chapter 10: NP Complete

NP - A class of problems

Longest Path Problem

Vertex Cover

NP Class Definitions

$X$: any decision problem
$I$: any (input) instance of X

Efficient Certifier for $X$:

• A polynomial time algorithm $A$ with output {yes, no}
• Input: ($I, s$), where $s$ is the certificate, usually a proposed solution
• Behaviour: There is a polynomial function $p$ such that $I$ is a yes-instance of X if and only if there exists a string $s$ with $|s| \leq p(|I|)$ such that $A$ outputs yes on i($input(I, s$).

Definition of NP

• The set of all decision problems which have an efficient certifier.
• NP = "Non-deterministic polynomial time"

Hamiltonian Cycle (HC)

• In Ham-Cycle, given a graph $G$, the problem is to decide whether there is a (simple) cycle that visits each vertex exactly once.
• Certificate is the cycle itself. Verifier checks in polynomial time whether it is a cycle and visits each vertex once.
• Hence, Ham-Cycle is in NP

P Class

Definition of P

• The set of all decision problems which have an efficient (poly-time) algorithm.
• What is the relationship between P and NP?

Certifier for P?
$X$: any decision problem in P
$I$: any (input) instance of X

• Let $Q$ be a polynomial time algorithm for solving $X$ Efficient Certifier for X:
• A polynomial time algorithm $A$ with output {yes, no}
• Input: $(I, s)$
• Behaviour: On getting input $(I, s)$, just ignore $s$ and execute the algorithm $Q$ on input $I$. If the answer is yes, output yes; if the answer is no, output no.

NP vs P

• Verifying a proposed solution versus finding a solution

NP Complete

• A problem $X$ in $NP$ class is $NP$-complete if for every $A$ in $NP$, they are poly-time reducible to X. $A \leq_p X$

• If $X$ is not known to be in $NP$, then we say $X$ is just $NP$-"hard".

Does any NP-Complete problem exist?

It really needs:

• courage to ask such a question and
• great insight to pursue its answer

Because:

• Every problem, known as well as unknown, from class NP has to be reducible to this problem.

Circuit Satisfiability Problem:

• Given a DAG with nodes corresponding to AND, NOT, OR gates and $n$ binary inputs, does there exist any binary input which gives output 1?
• Why is in NP?
  • Certificate is a binary input that gives output 1.

Question: How can every problem from NP be reduced to circuit satisfiability?
Answer:

• Consider any problem $A \in NP$.
• What we know is that it has an efficient certifier, say $Q$.
• Any algorithm which outputs yes/no can be represented as a DAG where internal nodes are gates, leaves are binary inputs, and output is 1/0. So Cook & Levin essentially transform $Q$ into the corresponding DAG and thus simulate $Q$ on the proposed solution.

Satisfiability (CNF-SAT)

• Literal: A Boolean variable or its negation. $x_i$, $\overline{x_i}$
• Clause: A disjunction (OR) of literals. $C_j = x_1 \lor \overline{x_2} \lor x_3$
• Conjunctive Normal Form (CNF): a formula $\Phi$ that is a conjunction (AND) of clauses. $\Phi = C_1 \land C_2 \land C_3 \land C_4$
• CNF-SAT: Given a CNF formula $\Phi$, does it have a satisfying truth assignment?

3-SAT

• SAT where each clause contains exactly 3 literals corresponding to different variables. $\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)$
• Satisfying assignment: $x_1 = \text{"True"}, x_2 = \text{"True"}, x_3 = \text{"False,"} x_4 = \text{"True"}$
• Unsatisfying assignment: $x_1 = \text{"True"}, x_2 = \text{"False"}, x_3 = \text{"False,"} x_4 = \text{"False"}$

Got it! Here's the corrected version with LaTeX math notation:

Proof for CNF-SAT being NP-Complete

To prove that if there is a polynomial-time reduction from the Circuit Satisfiability problem to the Conjunctive Normal Form Satisfiability problem (CNF-SAT), then CNF-SAT is NP-complete, we need to demonstrate two things:

CNF-SAT is in NP:

To show that CNF-SAT is in NP, we need to demonstrate that given a Boolean formula in Conjunctive Normal Form (CNF), we can verify whether it is satisfiable in polynomial time.

Verification in this case involves checking whether a given truth assignment satisfies all the clauses in the CNF formula. This process can be done in polynomial time by simply evaluating each clause and ensuring that at least one literal in each clause evaluates to true under the given truth assignment.

Since the verification process can be performed in polynomial time, CNF-SAT is in NP.

Reduction from Circuit Satisfiability to CNF-SAT:

Assuming we have a polynomial-time reduction from Circuit Satisfiability to CNF-SAT, we need to show that every problem in NP can be reduced to CNF-SAT in polynomial time.

Given an arbitrary problem A in NP, we can construct a polynomial-time reduction from A to Circuit Satisfiability (Circuit-SAT). Then, using the assumed polynomial-time reduction from Circuit-SAT to CNF-SAT, we can compose these reductions to obtain a polynomial-time reduction from A to CNF-SAT.

The composition of polynomial-time reductions preserves polynomial-time complexity, so if there exists a reduction from Circuit-SAT to CNF-SAT, then every problem in NP can be reduced to CNF-SAT in polynomial time.

Conclusion:

By demonstrating that CNF-SAT is in NP and showing that every problem in NP can be reduced to CNF-SAT in polynomial time given the assumed reduction from Circuit Satisfiability to CNF-SAT, we establish that CNF-SAT is NP-complete.

Therefore, if there is a polynomial-time reduction from Circuit Satisfiability to CNF-SAT, then CNF-SAT is indeed NP-complete.

NP Vs P

If any NP-complete problem is solved in polynomial time,

• $P = NP$

How to show a problem to be NP-complete?

Let $X$ be a problem we wish to show to be $NP$-complete:

• Show that $X$ is in $NP$
• Pick a problem $A$ which is already known to be $NP$-complete
• Show that $A \leq_p X$

Independent-Set

Definition: Given an undirected graph $G = (V, E)$, a subset $X \subseteq V$ is said to be an independent set if for each $u, v \in X, (u,v) \notin E$.

• Optimization Version: Compute the independent set of Largest Size.
• Decision Version: Does there exist an independent set of size $\geq k$?

Prove that 3-SAT $\leq_p$ Independent-Set

Given an instance $\Phi$ of 3-SAT, the goal is to construct an instance $(G, k)$ of Independent-Set so that $G$ has an independent set of size $k$ if and only if $\Phi$ is satisfiable.

Reduction:

• $G$ contains 3 vertices for each clause, one for each literal.
• Connect 3 literals in a clause in a triangle.
• Connect a literal to each of its negations.
• Set $k =$ "number of clauses".
• Reduction clearly runs in polynomial time.
• Suppose $\Phi$ is a YES-instance. Take any satisfying assignment for $\Phi$ and select a true literal from each clause. Corresponding $k$ vertices form an independent set in $G$.
• Suppose $(G, k)$ is a YES-instance. Let $S$ be the independent set of size $k$. Each of the $k$ triangles must contain exactly one vertex in $S$. Set these literals to true, so all clauses satisfied.

Worst Case Analysis

• Proof shows that some instances of "Independent-Set" are as hard to solve as the 3-SAT problem. This does not mean that all instances of the "Independent-Set" problem are hard!
• So, if there is no poly-time algorithm that solves 3-SAT on all instances, there is no poly-time algorithm that solves "Independent-Set" on all instances.
• A few things to notice:
  • Independent Set is NP-Complete
  • We also know, Independent Set $\leq_p$ Vertex Cover
  • So Vertex Cover is also NP-complete.
• Another Problem: Max-Clique: Given an undirected graph $G$ and an integer $k$, whether there exists a clique of size at least $k$ or not in $G$?
  • Exercise: Show Max-Clique is NP-complete (Hints: Try to prove Independent Set $\leq_p$ Max-Clique)

Hitting Set Problem

• For a set of sets $\{S_1, S_2, ..., S_n\}$, a set $H$ is said to be a hitting set if for all $S_i, H \cap S \neq \emptyset$ (i.e., $H$ has a non-empty intersection with all $S_i$).
• Hitting Set Problem: Given $\{S_1, ..., S_n\}$ and a non-negative integer $k$, decide whether there exists a hitting set of size at most $k$.
• Show that the Hitting Set Problem is NP-complete (Hints: Try a reduction from Vertex Cover)

Hitting Set is in NP

Status of SAT

• Fastest algorithm known for 3-SAT runs in time approximately $1.308^n$. It is believed that there is no $2^{o(n)}$-time algorithm for 3-SAT (Exponential Time Hypothesis).
• Often very convenient to reduce from 3-SAT to other problems, showing that those will also be hard if 3-SAT is hard.

Question

Suppose 3-SAT $\leq_p$ A for some decision problem A. Assume that there is no $2^{o(n)}$-time algorithm for 3-SAT. Then, there is no $2^{o(n)}$-time algorithm for A. True or false?

• False
• If the reduction runs in time $n^c$, then a $2^{o(n^{1/c})}$-time algorithm for A implies a $2^{o(n)}$-time

algorithm for 3-SAT.

• So by the assumption, there is no $2^{o(n^{1/c})}$-time algorithms for A.
• The lower bound for A depends on the running time of the reduction.