Turing Machine.pdf

(245 KB) Pobierz
INTRODUCTION TO THE THEORY OF
NP-COMPLETENESS
CSI4105: LECTURES 1-5
Lucia Moura
University of Ottawa
Fall 2002
Introduction to NP-completeness
These notes/slides are intended as an introduction to the theory of
NP-completeness, as a supplementary material to the first sections
in Chapter 34 (NP-completeness) of the textbook:
Cormen, Leiserson and Rivest,
Introduction to
Algorithms, 2nd ed, 2001.
Things that you will find here but not in this textbook include
definitions of basic models of computation (Turing machines and
the RAM model) and equivalence between models.
These concepts are important in order to have a formal definition
of “algorithms” and of their running times (rather than intuive
notions only).
These notes will take you from Letures 1 to 5, and include the
material in sections 34.1 and 34.2. After that, we will closely
follow the textbook and no notes will be provided.
Other references for these notes:
Garey and Johnson,
Computers and Intractability: a
guide to the theory of NP-completeness, 1979.
Sipser,
Introduction to the Theory of Computation, 1996.
Papadimitriou,
Computational Complexity, 1994.
Lucia Moura
1
A GENERAL INTRODUCTION TO
NP-COMPLETENESS
Introduction to NP-completeness
A general introduction
A practical application
Suppose your boss asks you to write an efficient algorithm to solve
an extremely important problem for your company.
After hours of hair-splitting, you can only come up with some
“brute-force” approach that, since you took CSI3501, you are able
to analyse and conclude that it takes exponential time!
You may find yourself in the following embarrassing situation:
/—— PICTURE —–/
(from Garey and Johnson page2)
“I can’t find an efficient algorithm, I guess I’m just too
dumb.”
Lucia Moura
3
Introduction to NP-completeness
A general introduction
You wish you could say to your boss:
/—— PICTURE —–/
(from Garey and Johnson page2)
“I can’t find an efficient algorithm, because no such algorithm
is possible!”
For most problems, it is very hard to prove their intractability,
because most practical problems belong to a class of well-studied
problems called NP.
The “hardest” problems in NP are the
NP-complete
problems:
if you prove that one NP-complete problem can be
solved by a polynomial-time algorithm, then it follows that all the
problems in NP can be solved by a polynomial-time algorithm.
Conversely, if you show that one particular problem in NP is
intractable, then all NP-complete problems would be intractable.
•
NP-complete problems seem intractable.
•
Nobody has been able to prove that NP-complete problems are
intractable.
Lucia Moura
4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin