NPCompleteness

NP-Completeness
 For convenience, the theory of NP-Completeness

is designed for decision problems (i.e. whose
solution is either yes or no).
 Abstractly, a decision problem consists simply
of a set Dof instances and a subset Y D
 We describe a decision problem by specifying a
generic instance and stating a yes - no question
 Examples: subgraph isomorphism and TSP
Decision Problems
 A decision problem can be obtained from an
optimization problem by adding a bound
 As long as the cost function is relatively easy
to compute, the decision problem can be no
harder than the optimization problem.
 The reason we restrict ourselves to decision
problems is that they have a natural
correspondence to formal languages.
Formal languages
 For any finite set of symbols  , we denote by  *
the set of all finite strings of symbols from  . For
example, if  = {0,1}, then  * consists of  , 0,1,
01,10,00,11,…….
 If L is a subset of *, we say L is a language over
the alphabet .
 An encoding scheme is a mechanism for describing
each instance of a problem  by an appropriate
string of symbols over some fixed alphabet  .
Problem Encodings
 Thus a problem  and encoding scheme e partition
* into three classes : those that are encoding of
"no", those that are encoding of "yes", and those
that are not a valid encoding at all.
 We define [ ,e] = { x   * :  is the alphabet of e
and x is the encoding under e of an instance I 
Y }
 We will say that if a result holds for L[ ,e] then it
holds for problem  under encoding scheme e
Problem Encodings
 Most properties that we will consider will be
essentially encoding independent so long as we
restrict ourselves to reasonable encoding schemes
 That is, if e and e are both reasonable encoding
schemes, then a property holds either for both
L[,e] and L[ , e ] or neither.
 This will allow us to say that the property holds
for  without specifying e.
Reasonable Encoding Scheme
 conciseness
 no unnecessary padding
 binary representation of numbers
 Decodability
 Given any particular component of a given
instance, one should be able to specify a
polynomial-time algorithm that is capable of
extracting its value from an encoded instance
Turing Machine
 Deterministic one_tape Turning Machine (DTM)
 Consists : finite state control, read_write head, and
a tape (2_way infinite)
 A program for a DTM specifies
 A finite set  of tape symbols which includes   
of i/p symbols and a distinct blank symbol b   - 
 A finite set Q of states which includes q0, qy, qN
  : (Q - { qy, qN} )    Q    { -1,1}
Turing Machine Operation
 i/p is a string x   * .
 x is placed in square 1…|x|. All others
contain blank.
 Program starts in state q0 at sequence 1.
 If current state is qy or qN then computation
has ended and the answer is "yes" or "no".
Complexity Classes
 P = { L :  polynomial time DTM m for
which L= Lm }
 NP = { L :  polynomial time NDTM m for
which L= Lm }
 NP can also be defined in terms of
polynomial-time verifiability
Verifiability
 Take TSP. Suppose someone claimed that
the answer for some instance is "yes".
 We could, if we were skeptical, ask this
person to prove their claim by providing us
with a tour.
 It would then be a simple matter to verify
the truth or falsity of their claim.
Verifiability
 It is this notation of polynomial time
verification that the class NP is intended to
isolate.
• Note that polynomial verifiability is
different from solvability
Polynomial Reducability
 A language L is NP-complete if L  NP and for all
other language L  NP, L  L
 If any single NP complete problem can be solved in
polynomial time, then all problems in NP can be
solved in polynomial time
 If any problem in NP-complete is intractable, then all
problems in NP-complete are intractable
 Once we have even a single NP-complete problem, it
becomes easier to prove NP-completeness
co-NP
• co-NP={L | complement(L) NP}
• Is (NP co-NP) - P non-empty?
Proving NP-Completeness
• A problem  is NP-complete if it satisfies
two properties:
– If  belongs to NP [this condition is sometimes
called being “NP-easy”]
– If every problem in NP can be reduced to  in
polynomial time [this condition is called being
“NP-hard”]

NPCompleteness

Uploaded by

Copyright:

Available Formats

NPCompleteness

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

NPCompleteness

Uploaded by

Copyright:

Available Formats

NP-Completeness

 For convenience, the theory of NP-Completeness

You might also like