Theory Of NP-Completeness

Theory of Completeness
It classifies the programming problems under two broad categories-

• Tractable
• Intractable

Tractable Problems

-a problem that is solvable by a polynomial-time algorithm.
-The upper bound is polynomial.
-Running in resourcable amount of time.
-NOT SO HARD problems
Eg. n,n^2 ,n lgn etc.

Intractable Problems

-a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential.
-HARD problems
-List all permutations (all possible orderings) of n numbers.

Eg. List all permutations (all possible orderings) of n numbers.