P vs NP

INTRODUCTION

NP vs P is highly theoretical topic with vast practical applications.
Lets see in short what does it mean informally:

• P class problems:  That can be solved in polynomial time. That is their upper bound is O(n^k), where k is some positive integer. Now, it doesn't matter how large k is : even if it 1000, we still call O(n^1000) as P class problem.
  
• NP class problems: Any problem that is not solvable in polynomial time, but can be "verified" in polynomial time is NP problem. What the heck does that mean? It simple means that there exists no algorithm to solve the problem within polynomial limits. It may be solved in 2^n time or n! time; however once we get the solution, we can check whether it is correct in polynomial time.
  For example, lets take an example of Hamiltonian Path Problem In this problem, we need to find a path in the graph such that it reaches every vertex only once, except the source vertex which is also a destination vertex. Till date, there is no proven polynomial time algorithm for same. However once the path is found, we can easily check in polynomial time, that whether such path really exists and satisfies the problem criteria.
  Note 1: When we see "not solvable in polynomial", we mean that no such algorithm has been yet discovered. It is always possible that in future some one discovers (or at least proves that there exists) a polynomial algorithm.
  Note 2: Since every problem in P class can be verified in polynomial time (do we really need to verify, we can solve it :P ), we can conclude that P is a subset of NP.
  
• NPC Class Problem: Informally, it means those problems which are "hardest" or at least no easier than any problem in NP class. We will get to technical definitions later, but it simply means that if any problem in NPC can be solved in polynomial time, all the problems in NP class will have polynomial time. 

Motivation

Before proceeding further, one may say, why the heck we need to study this section. How does it matter if the problem is n^1000 or 2^n, they both are practically impossible to implement for any sufficiently large value of n,  and so why bother to study them in separate sections? 

So, here are some of reasons why we should study P vs NP problems:

1. If a polynomial time algorithm is discovered for any problem, there is always chance that we can reduce its complexity further in polynomial time. O(n^1000) maybe with some improvements could work in O(n^100) or even smaller.
2. On other hand, if a problem is proved to be NP; it is always better to solve it be approximation algorithms or find algorithms for specific instances of problem, rather than trying to find a general solution which would work fast.
3. Polynomial problems also possess closure properties. Which in simple terms means that you add,  multiply, combine more than one polynomial algorithm, and you would still obtain polynomial solution. We cannot make such a claim about NP problems. 
4. Another thing that Polynomial problem has is that it tends to retain polynomial time on different kinds of computation model, such as Abstract Turing Machine; or Random Access computational model.
5. Although it is widely believed that no polynomial solution exists for any NPC problem, proving that such a solution exists will lead to polynomial solutions for EVERY NP problem. On the other hand, no one has been able to prove that such a solution should exist (or not!). This is indeed the most popular open question in Computer Science. (In case anyone is interested, there is $1,000,000 prize associated with it - to anyone who can prove whether a polynomial solution can exist for NPC problem or not)

Now lets move to technical bits:

DECISION vs OPTIMIZATION

Throughout, Algorithms study, we came across several Optimization problems, where our goal is to find an optimal solution to a given problem. For example, finding shortest distance between two nodes in a graph; or Longest Common Sub-sequence for two strings and so on...

However, in world of NP, we will deal with Decision problems. Our goal is not to find an optimal solution, but rather finding that "such solution exists." 

First, let us learn how to convert any optimization problem in decision problem. For shortest distance problem, 

Optimization: In a graph G(V, E), find the shortest path between nodes S and D.

Decision: In a graph G(V, E), does there exist a path between S and D which is of maximum weight W?

Easy!

Now, why we use decisions rather than optimizations? Well, because they are easy to answer! It is always easier to answer "yes" or "no" rather than find an optimal solution to a problem.

Also, remember we are now trying to prove "lower bounds" for problem, rather than "upper bound" : and so if we can prove that a decision problem is hard, we can conclude that Optimization problem is hard. 

So, in short our job is easier. If we can prove that a decision problem is hard, it automatically follows that corresponding optimization would be hard. On the other hand, if optimization is easy, decision problem is easier.

REDUCTIONS

This is fairly easy. Let's say, we have two decision problems: A and B. We have already solved A, and now we would like to solve B.

Now, there exists a BLACK BOX. What it does, it takes instance of problem B (which we would like to solve) and *magically* convert it into instance  of problem A (which we have solved). 

This Black Box has following properties:

• It is polynomial time conversion.
• Its conversion is "true" i.e. whatever is the answer of output ("yes" or "no" - keep in mind it is decision problem) is the answer of input.

So, this is a way, we show most problems are NPC, we take one problem which we already had proved to be "NPC", and then use some conversion algorithm and conclude whether next problem is NPC or not.

*****

This is in short: highly non-technical, very low level introduction to P vs NP problems. 

Further introductory studies might include:

1. Deterministic vs Non-Deterministic models
2. Examples of NPC Problems : Clique, vertex cover, 3-CNF, Hamiltonian Path, Subset Problem etc.

Source: CLSR