P and NP Problems

Last updated Nov 8, 2022 Edit Source

Hard Problems: the best-known algorithm for the problem is expensive in terms of running time.

Additionally:

• What is the minimum number of colours needed to colour a given undirected graph G such that each node is assigned a different colour from all its neighbours?
  • Given an undirected graph G and a natural number k, can G be coloured with more than k colours such that each node is assigned a different colour from all its neighbours?

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine.

$P\in NP$ because if a problem is solvable in polynomial time then a solution is also verifiable in polynomial time by simply solving the problem.

Non-deterministic polynomial time problems.

The class of decision problems for which they are solvable in polynomial time by a nondeterministic algorithm. Equivalently:

• A guess of the solution is generated by a nondeterministic algorithm
• It can be verified in polynomial time by a deterministic algorithm
• A solution by a deterministic algorithm in polynomial time has not yet been found

What is a nondeterministic algorithm:

Why is the Knapsack Problem in NP? Verification: There are $2^n$ subsets of n objects: to check all subsets we would need $O(2^n)$ time. However, given a guess of a subset: to check this subset we would need $O(n)$ time. Solution: DP Solution is Pseudo-Polynomial Time Complexity

• NP complete problems are equal to each other in difficulty
• Hardest problems in NP: if a NP-complete problem D can be solved in a certain amount of time, e.g. $O(f(n))$, every NP problem can be solved in $O(f(n))$ time. Hence no NP problem is harder than an NP-complete problem D.
• If a polynomial time solution can be found for an NP complete problem: P = NP

“At least as hard as the hardest problems in NP”. NP-Hard problems do not have to be in NP and do not have to be decidable.

A problem D is NP-Hard when for every problem L in NP, there is a polynomial time reduction from L to D. Equivalently:

• There is a polynomial time reduction from an NP-Complete problem G to D. Since all problems in NP can be reduced to G in polynomial time, G is also reducible to D in polynomial time.

Show that the Longest Path Problem is NP-Hard.

Reduction from the Travelling Salesman Problem: For a weighted complete graph G with non negative weights, the path that passes through all the vertices once must also be one of the longest paths because the longest path must include all vertices. Forgo the shortest path optimization in TSP and we obtain LPP.

Reduction from the Hamiltonian Path Problem: For an unweighted graph G, it has a Hamiltonian path if and only if its longest path has length n − 1, where n is the number of vertices in G. Because the Hamiltonian path problem is NP-complete, this reduction shows that the decision version of the longest path problem is also NP-complete. In this decision problem, the input is a graph G and a number k; the desired output is “yes” if G contains a path of k or more edges, and no otherwise.