Theory of Semi-Feasible Algorithms — Home Page

Theory of Semi-Feasible Algorithms

What this Page is About

Theory of Semi-Feasible Algorithms (Book), Lane A. Hemaspaandra and Leen Torenvliet, Springer-Verlag, ISBN 3-540-42200-5, 158 pages, 6 figures, 2003.
The book is released and available.



Click on the thumbnail to
see a larger photo.


Publisher's Blurb
List of Chapters
Preface, Table of Contents, and the Index
Order From Amazon
Publisher's Catalog Entry
How to Get A Desk Copy From The Publisher
Errata

Publisher's Blurb

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.

List of Chapters

Preface.
Introduction to Semi-Feasible Computation.
Advice.
Lowness.
Hardness for Complexity Classes.
Closures.
Generalizations and Related Notions.
Definitions of Reductions and Complexity Classes, and Notation List.
References.
Index.

Preface, Table of Contents, and the Index

Order the Book from Amazon.com.

Catalog Entry at the Publisher's North American Web Site.

How to Get A Desk Copy From The Publisher

If you are in North America and are seriously interested in possibly using the book as a course text, you can request a desk copy from Mike Spano of Springer-New-York (MSPANO@springer-ny.com). If you are outside of North America and are seriously interested in possibly using the book as a course text, you can request a desk copy from Ingeborg Mayer of Springer-Germany (I.Mayer@Springer.de). The book is relased and available.

Errata: (as pdf), (as postscript).







































Return to Top of Page