Scribd
Upload
22 views6 pages

Unit 5

Uploaded by

Harika Kopparthi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
22 views6 pages

Unit 5

Uploaded by

Harika Kopparthi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

The earlier chapters discussed about a variety of problems and algorithms.

Someof them are


straightforward, some are complicated and some are tricky, but virtually allof them
have complexity in o(n
3
) where n is inexactly described as the input size. From this point of view, this chapter deals
in accepting all algorithms studied so far as havinglow time requirements. Since many of
these problems are optimization problems
thata r i s e r e p e a t e d l y i n a p p l i c a t i o n s , t h e n e e d f o r a n e f f i c i e n t a l g o r i t
h m i s t h e a c t u a l significance.
Objective
This chapter deals with the class of vital problems that have some annoying property
of being efficiently solved. No reasonable fast algorithms for these problems have beenfound but
no one has been able to prove that the algorithms require a lot of time. At endo f t h i s l e s s o n
y o u ’ l l a b l e t o s h a r p y o u r s k i l l a n d k n o w l e d g e a b o u t N P - H a r d G r a p h Problems,
NP-Hard Code Generation Problems and NP-Hard Scheduling Problems.

B a s i c C o n c e p t s The problems that can be solved by a polynomial time algorithm and


problems for which no polynomial time algorithm is known should be a distinct. While the first
groupconsists of problems whose solution times are bounded by polynomials of small
degree,t h e s e c o n d g r o u p i s m a d e u p o f p r o b l e m s w h o s e b e s t - k n o w n
a l g o r i t h m s a r e n o n - polynomial.

Definition: The Class P


An algorithm is said to be polynomially bounded if its worst case complexity
is bounded by a polynomial function of its input size.Two classes of problems can be established
namely NP-hard and NP-complete. A problem that is NP-complete has the property that it
can be solved in polynomial time if and only if all other NP-complete problems can be solved in
polynomial time. If an NP-hard problem can be solved in polynomial time, then all NP-
complete problems can besolved in polynomial time. All NP-complete problems are NP-hard,
but the reverse is notalways true.The relationship of these classes to non-deterministic computations
together withthe apparent power of non-determinism leads to the intuitive conclusion
that no NP-complete or NP-hard problem is polynomially solvable.
Deterministic and Non-deterministic Algorithms
Algorithms, which use the property that the result of every operation is
uniquelyd e f i n e d , a r e t e r m e d
deterministic algorithms.
S u c h a l g o r i t h m s a g r e e w i t h t h e w a y programs are executed on a computer. Algorith
ms contain operations whose outcomesare not uniquely defined but are limited to specified
sets of possibilities. The machineexecuting such operations is allowed to choose any
one of these outcomes subject to
at e r m i n a t i o n c o n d i t i o n t o b e d e f i n e d l a t e r a n d t h i s l e d t o t h e
concept of a
non-deterministic algorithm.
New functions that are launched are given below:1 C h o i c e ( s ) a r b i t r a r i l y
chooses one
of the elements of set S.2Failure() signals an unsuccessful
completion.3Success() signals a successful
c o m p l e t i o n . The assignment statement x:=Choice(1,n) could result in x being assigned
any oneof the integers in the range [1,n]. There is no rule specifying how this choice is
to bemade. The Failure() and Success() signals, used to define a computation of the
algorithm,c a n n o t b e u s e d t o e f f e c t a
return.
A n o n d e t e r m i n i s t i c a l g o r i t h m t e r m i n a t e s unsuccessfully if and only if there exists no set
of choices leading to a success signal.

computing times for Choice, Success and Failure are taken to be O(1). Nondeterministicmachines
provide strong intuitive reasons to conclude that fast deterministic algorithmscannot solve certain
problems.
Example 1: Sorting: -
It sorts the numbers into ascending order and then outputs them in this order. Anauxiliary array
B[1:n] is used for convenience. Line 4 initializes B to zero. In the
for
loopof lines 5 to 10, each A[i] is assigned to a position in B. Line 7 non-
deterministicallydetermines this position. Line 8 makes sure that B[j] has not already been
used. Thus, theorder of the numbers in B is some permutation of the initial order in A.
The
for
loop of lines 11 and 12 verifies that B is sorted in ascending order. A successful
completion isachieved if and only if the numbers are output in nondecreasing order.
Since there isalways a set of choices at line 7 for such an output order, algorithm
Nsort is a sortingalgorithm. Its complexity is O(n). Recall that all deterministic
sorting algorithms musthave a complexity
Ω
(n log n).
Algorithm
Nsort(A,n) //Sort n positive integers{ for i:= 1 to n do B[i]:=0; //Initialize B[].For i:= 1 to n
do{ j:=Choice(1,n);if B[j]
≠
0 then Failure(); // B[j] already used// B{j]:= A[i];}for i:= 1 to n-1 do // Verify order.If B[i]>B[i+1] then
Failure();write (B[1:n]);Success(); }
Algorithm 8.1: Nondeterministic sortingDefinition : Decision Problem and Optimization Problem
Any problem for which the answer is either zero or one is called a
decision problem.
An algorithm for a decision problem is termed a
decision algorithm.
Any problem that involves the identification of an optimal value of a given cost function isk n o w n
as an
optimization problem.
An
optimization algorithm
i s u s e d t o s o l v e a n optimization problem.
Example 2: Maximum clique: -
A maximal complete subgraph of a graph G=(V,E) is a
clique.
The number of vertices determines the size of the clique. The max clique problemis an
optimization
problem that has to determine the size of a largest clique in G. The correspondingdecision problem
is to determine whether G has a clique of size at least k for some givenk. Let Dclique(G,k) be
a deterministic decision algorithm for the clique decision problem.If the number of vertices in G is
n, the size of a max clique in G can be found by makingseveral applications of Dclique. Dclique is
used once for each k, k=n,n-1, n-2,…, until theoutput from Dclique is 1. If the time complexity of
Dclique is f(n), then the size of a maxclique can be determined in time g(n), then the
decision problem can be solved in time g(n). Hence, the max clique problem can be solved in
polynomial time only if the cliquedecision problem can be solved in polynomial time.
Example 3:Max clique: -
The input to the max clique decision problem can be provided as a sequence of edges
and an integer k. Each edge in E(G) is a pair of numbers(i,j). The size of the inputfor each edge (i,j)
is [log
2
i]+[log
2
j]+2 if a binary representation is assumed. The input sizeof any instance isn=
∑
([log
2
i]+[log
2
j]+2) +[log
2

∈
k] + 1(i,j)

(G)i<j Note that if G has only one connected component then n


≥
|V|. Thus, if
thisd e c i s i o n p r o b l e m c a n n o t b e s o l v e d b y a n a l g o r i t h m o f c o m p l e x i t y
p ( n ) f o r s o m e polynomial p(), then it cannot be solved by an algorithm of complexity p(|V|).
Definition
The
time required by a nondeterministic algorithm
performing on any given inputis the minimum number of steps needed to reach a successful
completion if there exists asequence of choices leading to such a completion. In case
successful completion is
not possible, then the time required is O(1). A nondeterministic algorithm is of complexityO(f(n))
if for all inputs of size n, n
≥
n
0
, that result in a successful completion, the time required is at most cf(n) for some constants
c and n
0.
Example 4: Satisfiability: -
Let x
1
,x
2
,… denote boolean variables (their value is either true or false). Let

x
i
denote the negation of x
i
.A
literal
is either a variable or its negation. A formula in
the propositional calculus is an expression that can be constructed using literals and theoperations
and
and
or.
Examples of such formulas are (x

∧
1

x
2

∨
)

(x

∧
3

x
4
) and (x

∨
3

x
4

∧
)

(x

∨
1

x
2
∨
). The symbol

denotes
or

∧
and

denotes
and
. A formula is in
conjunctive normal form

∧
(CNF) if and only if it is represented as

k i=1
c
i
where c
i

∨
are clauses each representedas

l
ij
.The l
ij
are literals .It is in
disjunctive normal form

∨
( D N F ) i f a n d o n l y i f i t i s represented as

k i=1
c
i
and each clause c
i

∧
is represented as

l
ij
Thus (x

∧
1

x
2

∨
)

(x

∧
3

x
4
) is inDNF whereas (x
3
∨
x
4

∧
)

(x

∨
1

x
2
) is in CNF. The
satisfiability
problem is to determinewhether a formula is true for some assignment of truth-values to
the variables. CNF-
satisfiability
is the satisfiability problem for CNF formulas.
Algorithm DKP (p,w,n,m,r,x)
Page 164

You might also like