P, NP, NP Complete (note to self)

p_np_np_complete.md

Preamble

First, we can check the time needed to complete the following algorithm class:

1. O(N) -> say it requires 1 second to process N=100
2. O(N^3) -> 3 nested loops -> now requires N^3=1000000/100 * 1_second = 10000 seconds = ~ 3 hours
3. O(2^N) -> N levels (binary tree) of computations -> 2^N = 1.26e+30 seconds
4. O(n!) -> N levels (of increasing branches, 1x2x3x...xN) of computations -> 9.332622e+157 seconds

All about P

What is polynomial?

Math definition: an expression of more than two algebraic terms, especially the sum of several terms that contain different powers of the same variable(s).` Example: 6x4+3x3+3x2+2x+1 (Quartic Polynomial)

• N, N^k, etc are polynomial functions
• 2^N, N!, N^N, are non-polynomial functions

So in general, polynomial time refers to:

O(n^k) where n is the problem size, and k is a constant

Sample problems

• Adding n numbers: O(n)
• Sorting n items: O(n log n)
• Multiple 2 n by n matrices: O(n^2.37) --> PROVE IT
• Finding the shortest route between 2 points in a network with n roads (Dijkstra): O(n log n) --> more
• Solving a system of n linear equations: O(n^3)

What is P?

• Problems that can be solved in polynomial time
• Can be solved efficiently (does not hang the computer)
• Independent of
  • hardware (non-quantum)
  • operating system
  • programming language

What is not P?

• Travelling Salesman Problem
• Formula satisfiability

Now, what is NP (non-deterministic polynomial)?

Definition of NP

• The set of problems whose solution can be verified in polynomial time.
• A problem is called NP (nondeterministic polynomial) if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess.

a) Verification of TSP (distance travelled) Given permutation, is its length less than some value B

b) Verification of satisfiability Given a settings of the boolean variables, is the formula(statement) true?

c) Verification of sorting Given a list of numbers, is it already in sorted order? 4,5,1,3

So what is non-determinism here saying?

The non-determinism here comes from the fact that you can verify some solution that appear out of nowhere (maybe luck, maybe guess), but you cannot always replicate finding the solution quickly.

Also, the algorithm used can be different. We have 2 programs. 1 for verification, 1 for solution.However it is still 1 problem, an NP problem.

Moving on, NP-Completeness

This is a quest to seek the holy grail of P=NP, ie. can we solve NP quickly?

However, there are many different NP problems. Can we designate a "master problem", M of all NP problems so that if the master problem is solved, all NP problems are solved? This master problem is in the set of NP Complete. To be in NP Complete, M is already in NP, and every other problems in NP is quickly(in polynomial time) reducible/transformable to M. So if M is solved quickly, everything in NP will be solved quickly.

P != NP ?

Unsolved problem in computer science: If the solution to a problem is easy to check for correctness, must the problem be easy to solve? The P versus NP problem is a major unsolved problem in theoretical computer science.

NP Hard?

There isn't really a mathematical notion of NP hardness. It is at least as hard as the hardest problems in NP, and beyond. No need to sweat so much here.

Closing Remark: Deterministic Turing Machine

Read this about whether quantum computer can solve NP problems. It appears that the speedup of quantum computers are not at the same magnitude level of NP problems. Quantum computers have qubits, whereas our personal computers only have bits.

So what are indeterministic machines? Maybe it is like luck? Like hitting a lottery? Or probabilistic, educated guess? Find out more next time.