arvind

## @arvind

active 2 days, 8 hours ago
• P is the set of all decision problems that can be solved in polynomial time (by a deterministic Turing Machine). Polynomials are functions of the form sum(c_i xi). So, if there exist an algorithm solving problem X in O(xn) time where n is a natural number, we say X in P. An example is finding shortest path. Remember Dijkstra’s Algorithm? The fact that we can construct Dijkstra’s algorithm proves that the problem of finding shortest path of a non-negative weighted graph is a P problem.

NP is the set of all decision problems that, given an instance of solution, can be checked in polynomial time (by a deterministic Turing machine). For example, integer factorization is an NP problem because given a solution (say 2 . 2 . 2 is prime factorization of 23) we can decide in polynomial time if its true or false (in my example, it is false).

NP-Hard is the set of all decision problems that are at least as hard as the hardest NP problem. What does this mean? This means, every NP problem can be reduced to NP-Hard problems. If you have a solution to an NP-Hard problem, this means you have a solution to all NP problems, up to a polynomial time (deterministic) computation.

NP-Complete is the set of all problem that are both NP and NP-Hard. Famously, 3SAT (logical satisfaction problem), knapsack problem, Hamiltonian path etc… are NP-Complete problems. Given an instance of solution, you can decide in polynomial time if they are correct solutions to these problems. And every NP problem can be reduced to them.

It is a famous question of theoretical computer science whether P and NP are the same sets. Obviously, every P problem is an NP problem because in order to decide if a solution is correct, you can just solve the problem. If P=NP then every problem whose solution can be checked in polynomial time would be solved in polynomial time. If P!=NP then there would be at least one problem that can be verified but not solved in polynomial time. Notice that one possible way to prove P=NP can be finding a polynomial algorithm to an NP-Complete problem. But most complexity theorists do not expect a solution like this, and they expect to penetrate more into field and understand more about the algorithms in order to solve this problem.