NP-hard, Polynomial Time

http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm

http://bigocheatsheet.com/

http://cs.stackexchange.com/questions/9556/what-is-the-definition-of-p-np-np-complete-and-np-hard/18666#18666

http://ggnindia.dronacharya.info/csedept/Downloads/QuestionBank/Even/VI%20sem/ADA/Section-D/Basic_concepts_NP_Hard_NP_Complete.pdf

http://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

http://www.mathwarehouse.com/algebra/polynomial/polynomial-equation.php

Ø  O(1) – Constant Time Constant time means the running time is constant, it’s not affected by the input size.

Ø  O(n) – Linear Time When an algorithm accepts n input size, it would perform n operations as well.

Ø  O(log n) – Logarithmic Time Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm.

Ø  O(n log n) – Line-arithmic Time This running time is often found in "divide & conquer algorithms" which divide the problem into sub problems recursively and then merge them in n time. Example: Merge Sort algorithm.

Ø  O(n2) – Quadratic Time Look Bubble Sort algorithm!

Ø  O(n3) – Cubic Time It has the same principle with O(n2).

Ø  O(2n) – Exponential Time It is very slow as input get larger, if n = 1000.000, T(n) would be 21000.000. Brute Force algorithm has this running time.

Ø  O(n!) – Factorial Time THE SLOWEST !!! Example : Travel Salesman Problem (TSP)

Ø  O(1) - constant time

Ø  O(log(n)) - logarithmic time

Ø  O((log(n))c) - poly-logarithmic time

Ø  O(n) - linear time

Ø  O(n2) - quadratic time

Ø  O(nc) - polynomial time

Ø  O(cn) - exponential time

A Polynomial can be expressed in terms that only have positive integer exponents and the operations of addition, subtraction, and multiplication. In other words, it must be possible to write the expression without division.

Examples of Polynomials

P:

It is the set of all decision problems solvable in polynomial time. We will generally refer to these problems as being “easy” or we will generally refer to these problems as being easy or “efficiently solvable”

Pis the class of decision problems that can be solved efficiently, i.e. decision problems which have polynomial-time algorithms.

Assume that efficient algorithms means algorithms that use at most polynomial amount of computational resources. The main resource we care about is the worst-case running time of algorithms with respect to the input size, i.e. the number of basic steps an algorithm takes on an input of size n. 

NP: 

Set of all decision problems that can be verified in polynomial time.

If I claim that there is a polynomial time solution for a particular problem, you ask me to prove it. Then, I will give you a proof, which you can easily verify in polynomial time. These kind of problems are call NP problems. Note that, here we are not talking about whether there is a polynomial time solution for this problem or not. But we are talking about verifying the solution to a given problem in polynomial time.

NP= Problems with Efficient Algorithms for Verifying/ Proofs/Certificates/Witnesses

Sometimes we do not know any efficient way of finding the answer to a decision problem, however if someone tells us the answer and gives us a proof we can efficiently verify that the answer is correct by checking the proof to see if it is a valid proof. This is the idea behind the complexity class NP.

P and NP:

P⊆NP

Therefore we have P=efficient solvable and NP=efficiently verifiable. So P=NPif the problems that can be efficiently verified are the same as the problems that can be efficiently solved.

Note that any problem in P is also in NP i.e. if you can solve the problem you can also verify if a given proof is correct: the verifier will just ignore the proof.

class of efficiently solvable problems (

P) and the class of problems efficiently verifiable problems (NP). As we discussed above, both of these are upper-bounds.

NP-complete:

These are the problems, which are both NP and NP-Hard. That means, if we can solve these problems, we can solve any other NP problem and the solutions to these problems can be verify in polynomial time.

NP-hard: 

These are the hardest problems. If we can solve these problems in polynomial time, we can solve any other NP problem that can possibly exist.

• These problems are not NP problems.

• We may/may-not verify the solution to these problems in polynomial time.

What does NP-hard mean? A lot of times you can solve a problem by reducing it to a different problem. I can reduce Problem B to Problem A if, given a solution to Problem A, I can easily construct a solution to Problem B. (In this case, "easily" means "in polynomial time.")

If a problem is NP-hard, this means I can reduce any problem in NP to that problem. This means if I can solve that problem, I can easily solve any problem in NP. 

All NP-Complete problems are NP-Hard but not all NP-Hard problems are not NP-Complete.

Deterministic and Non-deterministic Algorithm:

When the result of every operation is uniquely defined then it is called deterministic algorithm. When the outcome is not uniquely defined but is limited to a specific set of possibilities, we call it non deterministic algorithm.

What exactly is the difference between NP-hard and NP-complete problems? - ResearchGate. Available from: https://www.researchgate.net/post/What_exactly_is_the_difference_between_NP-hard_and_NP-complete_problems [accessed May 12, 2016].

http://ggnindia.dronacharya.info/csedept/Downloads/QuestionBank/Even/VI%20sem/ADA/Section-D/Basic_concepts_NP_Hard_NP_Complete.pdf