2. Computable Functions & NP-completeness

Computable Functions

Computable function

A function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ on words from ${\Sigma }^{\ast }$ is computable if there is a deterministic Turing Machine $M_f$ s.t.: (or there is a lambda-term)

• $M_f$ accepts all input words $w\in {\Sigma }^{\ast }$
• when started in configuration $(q_{\text{init}},ϵ,w)$, the machine eventually terminates in configuration $(q_{\text{accept}},ϵ,f(w))$.

The machine transforms the contents of the tape from $w$ to $f(w)$ and returns the tape head to the start of the word.

Link to original

Polynomial Reduction

Polynomial Reduction

A polynomial reduction from a problem $X$ to problem $Y$ is a function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ computable in polynomial-time such that:

$$\begin{array}{c}w\in X⟺f(w)\in Y\\ X{\le }_{p}Y\text{ means }X\text{ is polynomially reducible to }Y\end{array}$$Link to original

NP-hard

A problem $X$ is NP-hard if every problem in NP can be polynomially reduced to it.

$$Y{\le }_{p}X\text{ for all }Y\in \text{NP}$$Link to original

NP-complete

A problem $X$ is NP-complete if:

• $X$ is also NP-hard
• $X$ also belongs to NP

Link to original

Proving NP-hardness

If $Y$ is NP-hard and $Y{\le }_{p}X$, then $X$ is also NP-hard.

1. Suppose that: (i) $Y$ is NP-hard and (ii) $Y{\le }_{p}X$
2. By (i), we have $Z{\le }_{p}Y$ for all $Z\in NP$
3. By (ii) and transitivity, we have $Z{\le }_{p}Y{\le }_{p}X$ for all $Z\in NP$

A typical approach to demonstrating that a problem is NP-hard is to show that Boolean Satisfiability Problem (SAT) is reducible to it.

$$SAT{\le }_{p}X$$