عنوان

Theory of Semi-Feasible Algorithms

(Number (ISBN

3662050803

(Number (ISBN

9783662050804

Number

b579373

Title Proper

Theory of Semi-Feasible Algorithms

General Material Designation

[Book]

First Statement of Responsibility

by Lane A. Hemaspaandra, Leen Torenvliet.

Place of Publication, Distribution, etc.

Berlin, Heidelberg

Name of Publisher, Distributor, etc.

Springer Berlin Heidelberg

Date of Publication, Distribution, etc.

2003

Specific Material Designation and Extent of Item

(x, 149 pages)

Series Title

Monographs in Theoretical Computer Science An EATCS Series.

Text of Note

1. Introduction to Semi-Feasible Computation --; 2. Advice --; 3. Lowness --; 4. Hardness for Complexity Classes --; 5. Closures --; 6. Generalizations and Related Notions --; A. Definitions of Reductions and Complexity Classes, and Notation List --; A.1 Reductions --; A.2 Complexity Classes --; A.3 Some Other Notation --; References.

Text of Note

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.

Computational complexity.

Computer science.

Computer software.

Class number

Book number

by Lane A. Hemaspaandra, Leen Torenvliet.

Lane A Hemaspaandra

Leen Torenvliet

Electronic name

[Book]

Y