This post depicts what I have learnt from my favorite teachers. All the idea I have borrowed from their classes. I gratefully thank Dr. Demaine and Dr. Fuentes for their great course materials [1], [2].
Polynomial
If you raise a non-negative positive number to the power of a variable, you get a polynomial. So x ^ 0, x^1, x^3 are all polynomials but x ^ -1 or x ^ 3.4 is not polynomials.
P
If an algorithm solves a problem of input size n in n ^ c steps where c is a non-negative integer, then that is is polynomial time algorithm.
Example:
bubble sort algorithm O(n^2)
merge sort algorithm O(nlogn) [it is less than a polynomial n^2]
Djkastra's algorithm to find single-source shortest path O(V+E) [V = vertices, E = Edges]
NP (Non Deterministic Polynomials)
An algorithm exponential problem if for input size n, it takes constant ^ n time solve the algorithm. The whole universe has 10 ^ 80 fundamental particles. So, for an exponential algorithm, with input size 80, it might not be possible to solve the problem if you turn all the fundamental particles into a computer.
An exponential algorithm would search all the possible solutions to find a problem. Lets talk about the knap-sack problem. Basically, you are given a bag and a list of items. The bag has a maximum capacity. You know the weight and values of different items. Here is a sample example input
Your task is to fill the bag with maximum value items. A usual computer would iterate through all the possible subsets that can be generated from n items which is 2^n. The following picture gives idea how a usual computer would solve the problem.
001 at the end of the recursion means, it is checking the possibility where it will not take item1 and 2 but will take item3.
If somehow we have a non-deterministic computer, that knows what do with each item, we can solve the problem in linear time. As you can see in the picture. As soon as it looks at the item1, the algorithm just knows it will not take it, as soon as it looks at item 2 and 3, it knows it should take these items. Those problems that a non-deterministic computer can solve in polynomial time are called NP problem.
NP Complete
NP Complete algorithms are those that checks exponential number of solutions. Each solution should be solved in polynomial time. These are considered the hardest NP problems. Example can be knapsack problem, traveling salesman problem.
NP Hard
NP hard problems consists of problems from NP Complete problems and contains all other problems. Most of NP Hard problems are unsolvable. For example Alan Touring's Halting problem.
The Diagram of computational hardness is shown in below.
Polynomial
If you raise a non-negative positive number to the power of a variable, you get a polynomial. So x ^ 0, x^1, x^3 are all polynomials but x ^ -1 or x ^ 3.4 is not polynomials.
P
If an algorithm solves a problem of input size n in n ^ c steps where c is a non-negative integer, then that is is polynomial time algorithm.
Example:
bubble sort algorithm O(n^2)
merge sort algorithm O(nlogn) [it is less than a polynomial n^2]
Djkastra's algorithm to find single-source shortest path O(V+E) [V = vertices, E = Edges]
NP (Non Deterministic Polynomials)
An algorithm exponential problem if for input size n, it takes constant ^ n time solve the algorithm. The whole universe has 10 ^ 80 fundamental particles. So, for an exponential algorithm, with input size 80, it might not be possible to solve the problem if you turn all the fundamental particles into a computer.
An exponential algorithm would search all the possible solutions to find a problem. Lets talk about the knap-sack problem. Basically, you are given a bag and a list of items. The bag has a maximum capacity. You know the weight and values of different items. Here is a sample example input
Item Weight Value
1 6 2
2 2 4
3 3 5
Bag Capacity 6
Your task is to fill the bag with maximum value items. A usual computer would iterate through all the possible subsets that can be generated from n items which is 2^n. The following picture gives idea how a usual computer would solve the problem.
001 at the end of the recursion means, it is checking the possibility where it will not take item1 and 2 but will take item3.
If somehow we have a non-deterministic computer, that knows what do with each item, we can solve the problem in linear time. As you can see in the picture. As soon as it looks at the item1, the algorithm just knows it will not take it, as soon as it looks at item 2 and 3, it knows it should take these items. Those problems that a non-deterministic computer can solve in polynomial time are called NP problem.
NP Complete
NP Complete algorithms are those that checks exponential number of solutions. Each solution should be solved in polynomial time. These are considered the hardest NP problems. Example can be knapsack problem, traveling salesman problem.
NP Hard
NP hard problems consists of problems from NP Complete problems and contains all other problems. Most of NP Hard problems are unsolvable. For example Alan Touring's Halting problem.
The Diagram of computational hardness is shown in below.
References
I remember that Dr. Kreinovich also used the example of the particles as processing units during Theory of Computation. Great times. Great posts, brother, I'm glad you are doing this. Just being curious, have you continued learning spanish?
ReplyDeleteI am learning a lot of things, Spanish is and always will be one of the those things.
Delete