|
|
16 of 16 people found the following review helpful:
5.0 out of 5 stars
On the difficulty of computers to deal with certain problems, April 16, 1997
By A Customer
All those who deals with Computer Science,
Mathematics and Engineering have to face the
reality that certain problems seem really hard
to solve. Even with the more sophisticated, and
technologically advanced among the currently
available computers---and among those that are to
come in the next several years---, it seems highly
likely that we cannot efficiently solve certain
specific problems.
A first well written and systematic account on
the hardness of this problems is the 1979 book on
the theory of NP completeness by Michael R. Garey
and David S. Johnson: Computers and
Intractability, A Guide to the Theory of
NP-Completeness (W.H. Freeman and Company, San
Francisco). It is amazing how, after all these
years, this book remains a fundamental one to be
introduced on what can be effectively and
efficiently solved by computers and above all on
what it seems not efficiently solvable,
independently of the advances of technology.
Other texts have been published after that one,
as for example the recent clear and complete
overview on what has been done and extensively
researched since then that has been given by
Christos H. Papadimitriou in his book
Computational Complexity (Addison-Wesley, 1994).
Nevertheless, the Garey-Johnson book---as it is
often familiarly called---remains the fundamental
book for a clear introduction to this central
problem of what is tractable by computers.
Starting from a very clear introduction to the
technical term "NP-Complete," and to how this
term gained importance for the description of the
algorithmic tractability of certain problems in
the early 70s, the book clearly defines, both in
an intuitive and then in a formal way, what it is
meant by the complexity of a problem. More than
that, this complexity is directly related to the
effective methods for solving problems
(algorithms) and thus to computers themselves.
The basic of the theory of NP-Completeness is
completely covered in the first 5 chapters,
beginning from a low-level introduction to some
of the central notions of computational
complexity and finally providing detailed
definitions describing proof techniques to prove
the hardness of certain problems. The remaining
two chapters provide an overview on two
alternative directions for further study. (The
both of them have been extensively investigated
in the following years.) Finally, the appendix
contains more than 300 main entries on
NP-Complete and NP-Hard problems, and this last
part of the book is continuously referenced in
journal and conference papers on the subject.
The first chapter is definitely accessible also
to those that doesn't know so much mathematics,
or computers related stuff, and thus the book is
recommendable to those that are simply curious
about the things that can be solved with
computers.
|
by Vijay V. Vazirani
by Christos H. Papadimitriou
by Michael Sipser
by Sanjeev Arora
