NP-Completeness

Theory of NP-Completeness

P(Polynomial):Problems involving algorithms taking polynomial amounts of time to solve.

OR

Set of problems that can be solved by a deterministic turing machine in polynomial time.They are solved easily thereby called Tractable Problems.

1. For example:O(1),O(n),
2. O(n2)-QuickSort
3. Merge and Quick Sort-O(nlogn),
4. Binary Search-O(n),
5. Searching,
6. Element Uniqueness(No duplication),
7. Graph Connectivity

NP(Non-deterministic Polynomial):

Set of problems that can be solved by a non-deterministic turing machine in polynomial time.They are difficult to solve,easy to check a given answer. If you introduce nondeterministic Turing machines and appropriately define “polynomial time,” then NP is the set of problems that an NTM can solve in polynomial time.

For example:

1. Travelling Salesman Problem,
2. Knapsack Problem,
3. Shortest Path,
4. Vertex Cover,
5. Minimum Spanning Tree

NP-compete(Non-deterministic Polynomial Complete): A decision problem L is NP Complete if:

1. A is NP
2. Every problem in NP is reducible to A in polynomial time.
3. For example:Cryptography
4. Chess
5. Long Simple Paths

• A problem is in the class NPC if it is in NP and is as hard as any problem in NP.
• A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself.
• P being the subset of NP and NP-Complete being the subset of NP-Hard.

Class Relationship of P, NP & NP Complete:

• P is easy in difficulty level(Path Problem).
• NP gives Graph is isomorphic(conjectured) and is medium in difficulty level.
• NP Complete is hard in difficulty level.
• NP Hard being the hardest in difficulty level.

Relationship between P and NP(P ⊆ NP):

• If P = NP:
  •  A huge number of seemingly difficult problems could be solved efficiently.
  • Our capacity to solve many problems will scale well with the size of the problems we want to solve. 
• If P ≠ NP:
  • Enormous computational power would be required to solve many seemingly easy tasks.
  • Our capacity to solve problems will fail to keep up with our curiosity.