ELEMENTS OF THE THEORY OF COMPUTATION

Lewis and Papadimitriou present this long awaited SecondEdition of their best-selling theory of computation. The authors arewell-known for their clear presentation that makes the material accessible to aa broad audience and requires no special previous mathematicalexperience. In this new edition, the authors incorporate asomewhat more informal, friendly writing style to present both classical andcontemporary theories of computation. Algorithms, complexity analysis, andalgorithmic ideas are introduced informally in Chapter 1, and are pursuedthroughout the book. Each section is followed by problems.