Proving NP-Hardness

Question 1

Why is proving that problems are NP-Hard challenging?

Answer 1

Because 3-SAT or SAT is structurally very different to many problems that we believe to be in this class

Question 2

What is the Hamiltonian Cycle Problem?

Answer 2

The decision problem that takes a directed graph and outputs yes if there is a directed path that starts at one node, visits each other node in the graph then returns to the start node.

Question 3

What does P != NP imply?

Answer 3

• NP - Hard problems are not in P
• There are no polynomial time algorithms for the most difficult problems in NP

Question 4

What does P = NP imply?

Answer 4

• Even the most difficult problems in NP (the ones that are NP-Hard) are also in P
• There is a polynomial time algorithm for every problem in NP

Question 5

What makes many people believe that P != NP?

Answer 5

We have not yet been able to find a polynomial time solution for any of the many NP-Hard problems

We are good at finding algorithms and bad at proving they do not exist

Question 6

How can we prove that a problem is NP-Hard?

Answer 6

With our problem ‘x’ we can take a known NP-Hard problem ‘a’ and:

• Take an instance of ‘a’ and convert it to problem ‘x’ in polynomial time of ‘a’
• Solving problem ‘x’ would then yield a solution to problem ‘a’

This proves that ‘x’ is np hard because if you know how to solve ‘x’, then you know how to solve ‘a’, and since ‘a’ is np hard ‘x’ must also be np hard