NP-completeness

Question 1

What is a computable function

Answer 1

A function f : Σ∗ → Σ∗ on words from Σ∗
is computable if there is a
(deterministic) Turing Machine Mf such that:

.M accepts w for all w ∈ Σ∗ (strings formed from alphabet)
. When started in configuration
(qinit, ε, w) the machine eventually
terminates in configuration qaccept, ε, f(w)

ie - contents of tape changed from w(input string) to f(w) the output with the tapehead to the start of the output

Question 2

polynomial reduction

Answer 2

A polynomial reduction from a problem X to a problem Y is a
function f : Σ∗ → Σ∗ computable in polynomial-time such that
w ∈ X ⇐⇒ f(w) ∈ Y
X ≤p Y means X is polynomially reducible to Y

Question 3

summary of polynomial reduction

Answer 3

If we have two problems, X and 𝑌:
. We can transform any instance w of problem X into an instance 𝑓(𝑤) of problem 𝑌 efficiently, i.e., in polynomial time.

. Solution properties are preserved (if answer on input w in X is Yes answer for f(w) in Y is also Yes)

. if you can solve f(w) ( instance of Y) efficiently you can solve w ( instance of X) efficiently by using function to transform w to f(w) and using Y’s solution as transformation preserves solution properties

Question 4

X ≤p Y
is X or Y harder

Answer 4

Y is at least as hard as X since the way to solve X is transforming an input of X to an input of Y and using Y’s solution to determine what X’s solution is

Question 5

NP hardness

Answer 5

A problem is said to be NP-hard if every problem in NP can be polynomially reduced to it

Y ≤p X for all Y ∈ NP
X is at least as hard as all NP problems

Question 6

relationship between NP hardness and P = NP

Answer 6

. Every NP problem can be reduced to an NP- hard problem in polynomial time (efficiently)
. if you can solve an NP hard problem efficiently you can solve every NP Problem efficiently (due to preservation of solution properties)
. This would mean P = NP
as you have shown NP problems(which before could only be verified efficiently) can be solved efficiently

Question 7

Prove NP- hardness
Theroem If Y is NP-hard and Y ≤p X , then X is also NP-hard

Answer 7

Proof :
1) Y IS NP-HARD
Z ≤p Y for z ∈ NP
2) transitivity:
if Z ≤p Y and Y ≤p X
Z ≤p Y ≤p X
therefore Z ≤p X Z ∈ NP
- this means X is NP hard as all NP problems can
polynomially reduced to X

Question 8

NP complete

Answer 8

. X is NP-hard (lower bound) at least as difficult as hardest problems in NP

. X also belongs to NP
- worst case time to verify a solution does not exceed
polynomial time