Slide#01
Nondeterministic-Polynomial (NP)
Slide#02Outlines
vNP
vDeterminism
vs
Nondeterminism
vAlgorithm
vNP
Hard
vNP
Complete
vProblems
in NP
vExample(TSP) Slide#03
Non-Polynomial
vSet
of
all
problems
that
can be solved by non-deterministically in
Polynomial Time.
vThe
class
of decision problems that are verifiable
in polynomial time.
vComplexity:
Every problem
in this class can be solved in exponential time
Exponential time
O(cn)
where is c is a positive constant >1
vEx: n=
10 n=20 n=30 n=40 n=50
O(2n) 0.001s 1s 17.9min 12.7days 35.7years
vNP
class
– non-deterministic polynomial
time, the
solutions
for the problems are intractable.
Slide#04
Determinism vs. Nondeterminism
v
Nondeterministic algorithms consists of
vPhase
1: Guessing(In different Choices)
vPhase
2: Checking
Choice(X) :
chooses any value randomly from the set X.
failure()
:
denotes the unsuccessful solution.
success()
:
Solution is successful and current thread terminates.
v Deterministic algorithm
is (essentially) one that always computes the correct
answer
v
Slide#05
Algorithm
Problem Statement :
Search
an
element x on A[1:n] where n>=1,
on successful search return j if a[j] is equals to x otherwise return 0.
1.j=
choice(a, n)
2.if(A[j]==x)
then
{
write(j);
success();
}
3.write(0);
failure();
Slide#06
Sample
Problems in NP
vFractional
Knapsack
vSingle-source
shortest path
vSorting
vOthers?
ØKnapsack
ØTraveling
salesman problem (TSP)
ØHamiltonian
Cycle Problem
ØSatisfiability
(SAT)
ØConjunctive
Normal Form (CNF) SAT
Ø3-CNF
SAT
Slide#07
NP-Hard
Problems
vA
problem is NP-hard if every problem in NP is reducible
to it.
vBasically
means that NP-hard problems are at least as hard
as the hardest problems in NP.
vNeed
exponential time to find optimal solutions.
vImportant:
For
a problem to be NP-hard it does not have
to be in class NP
Slide#08
NP-Complete
Problems
vNP
+ NP-Hard
vThe
group of problems which are both
in NP and NP-hard are known as NP-Complete
problem.
vNP-Complete”
comes from:
Nondeterministic Polynomial
Complete - “Solve one, Solve them all”
New problems
can be added to NP-Complete if
the following
two
conditions are satisfied:
ØThe
new problem can be reduced into one of the
existing problems
in NP-Complete.
ØAn existing NP-Complete problem can
be reduced into the
new problem.
Slide#09
Traveling
Salesman Problem (TSP)
vThe well-known traveling salesman problem:
vYou have to visit n cities
vVisiting each city exactly once and
finishing where he begins.
vHow to minimize travel time?
Slide#10
In
4 cities problem
vIn case
of four cities, you have three solutions
✓ A-B-C-D-A,
✓ A-B-D-C-A,
✓ A-D-B-C-A
vThere
will
not be any other possibilities here
vSo possibilities
are given by (n-1) ! /2
vFor
3
cities, 1 possibility. 4 cities 3!/2 =3 possibilities
Slide#11
Is
TSP Hard Problem??
vIn
case of 31 cities, you will have 30!/2 solutions
vIf
a computer can do 106
calculations in 1 second, then it will take
v30!
/ (2* 106
) seconds
vOr
30! / (2* 106 *24*60*60)
days
vOr
30! / 365*(2* 106
*24*60*60) years = 6.3* 1013
vWhich
is more than the life of earth.
vSuch
problems are called NP Hard problem.
Slide#12
Summary
vNP
(nondeterministic polynomial-time): the class of decision
problems that
are verifiable
in polynomial time.
vNP-hard: A problem
is NP-hard if every problem in NP is reducible
to it.
vNP-Complete: Optimization/Decision Problems.
No comments:
Post a Comment