13-12-2012, 06:25 PM
NP COMPLETE and NP HARD
NP COMPLETE.ppt (Size: 216.5 KB / Downloads: 27)
Introduction
Problems classified to belong to one of the two groups:-
1. Problems with solution times bound by a polynomial of a small degree
– Most searching and sorting algorithms
– Also called tractable algorithms
2. Problems with best known algorithms not bound by a polynomial
– Hard, or intractable problems
– Traveling salesperson (O(n2 2n)), knapsack (O(2n/2))
– None of the problems in this group has been solved by any polynomial time algorithm
Basic concept
Some problems are intractable(Difficult): As they grow large, we are unable to solve them in reasonable time.
What constitutes reasonable time?
Standard working definition: polynomial time
Definition :- On an input of size n the worst-case running time is O(nk) for some constant k.
Ex. :- O(n2), O(n3), O(1), O(n lg n), O(2n), O(nn)
Polynomial time: O(n2), O(n3), O(1), O(n lg n)
Not in polynomial time: O(2n), O(nn)
Polynomial-Time Algorithms
Are some problems solvable in polynomial time?
Of course: many algorithms we’ve studied provide polynomial-time solutions to some problems.
Are all problems solvable in polynomial time?
No: Turing’s “Halting Problem” is not solvable by any computer, no matter how much time is given.
Most problems that do not yield polynomial-time algorithms are either optimization or decision problems.
The Class P
Definition: The class of decision problems that have polynomial-time deterministic algorithms.
That is, they are solvable in O(p(n)), where p(n) is a polynomial on n
A deterministic algorithm is (essentially) one that always computes the correct answer
Why polynomial?
if not, very inefficient
nice closure properties
the sum and composition of two polynomials are always polynomials too