Theory of Semi-Feasible Algorithms
By: by Lane A. Hemaspaandra, Leen Torenvliet
Contributors: Torenvliet, Leen
Series: Monographs in Theoretical Computer Science An EATCS Series; Monographs in Theoretical Computer Science An EATCS Series
Publisher: Springer Berlin Heidelberg
Published: 2003
Place of publication: Berlin, Heidelberg
Language: eng
Format: [electronic resource] /
Number of pages: 149
ISBN-13: 9783642075810; 9783662050804
Subjects: Combinatorics; Computational complexity; Algorithms; Computer science; Computer software
Description: This book presents a consolidated survey of the vibrant field of research known as the theory of semi-feasible algorithms. This research stream perfectly showcases the richness of, and contrasts between, the central notions of complexity: running time, nonuniform complexity, lowness, and NP-hardness. Research into semi-feasible computation has already developed a rich set of tools, yet is young enough to have an abundance of fresh, open issues. Being essentially self-contained, the book requires neither great mathematical maturity nor an extensive background in computational complexity theory or in computer science in general. Newcomers are introduced to the field systematically and guided to the frontiers of current research. Researchers already active in the field will appreciate the book as a valuable source of reference.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.