Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0833.68049
Papadimitriou, Christos H.
Computational complexity. (English)
[B] Amsterdam: Addison-Wesley Publishing Company. xv, 523 p. US\$ 40.95 /hc (1994). ISBN 0-201-53082-1

The book contains an introduction to the complexity theory at the graduate level. It describes in a comprehensive way such issues as: problems and algorithms, Turing machines as a universal model of computations, logic (Boolean, first-order and second-order) as the most important application to be studied. Then complexity classes are discussed in detail, starting with relations between them and including the concept of completeness (in class P and NP). Later NP-complete problems are described together with proof methodology. Class of co-NP problems, randomized computations and cryptography are discusses in a sequel. This part of the book is complemented by a discussion of approximability and the basic question ``N$=$NP?'' including intermediate degrees, isomorphism and density, and oracles.\par The next part of the book discusses the detailed structure of class P, concentrating on parallel algorithms and logarithmic space complexity.\par Finally, several complexity issues concerned with problems beyond class NP are analyzed. They include polynomial hierarchy, polynomial space and a discussion of exponential time complexity. Summing up, the book is well written and requires almost no mathematical prerequisites. Its main drawback is that it leaves the main question ``P$=$NP?'' still open.
[J.Błazewicz (Poznań)]

MSC 2000:: *68Q15 Complexity classes of computation
03D15 Complexity of computation
03D10 Turing machines and related notions
68-01 Textbooks (computer science)
68Q05 Models of computation

Keywords: complexity theory; Turing machines; NP-complete problems

Cited in: Zbl 1147.68608 Zbl 1145.03314 Zbl 1002.90100 Zbl 1001.68050 Zbl 0944.90066 Zbl 0895.68070

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]