Theory of semi-feasible algorithms (Q5959347)

From MaRDI portal
scientific article; zbMATH DE number 1723372
Language Label Description Also known as
English
Theory of semi-feasible algorithms
scientific article; zbMATH DE number 1723372

    Statements

    Theory of semi-feasible algorithms (English)
    0 references
    0 references
    0 references
    1 April 2002
    0 references
    The book systematic collects and represents results from semi-feasible computation field. Doing so the book unifies semi-feasibility research and makes it accessible. The text is divided into 6 chapters. The first chapter is introduction to semi-feasible computation. Here are introduced \(P\)-selectivity and nondeterministic selectivity. The second chapter deals with advice strings and circuits. The advices of both types are considered: the advice for \(P\)-selective sets, and the advice for nondeterministically selective sets. The third chapter is dedicated to lowness. Firstly basic lowness theory is introduced and then follow lowness of \(P\)-selective sets, and lowness of nondeterministically sets. Hardness for complexity classes is a subject of the chapter 4. The chapter gives an answer to questions connected with the hardness of \(P\)-selective sets, and nondeterministically selective sets. The fifth chapter is devoted to closures. A stress is given to the study of several closure properties of the \(P\)-selective sets. Also the study of the combination of self-reducibility and selectivity is covered here. The chapter 6 mainly describes some generalizations and refinements of \(P\)-selectivity. Reading of the book does not suppose any knowledge of semi-feasible computation. The book may be used as a core of a second course on computational complexity theory, and is at least an important information source for researchers.
    0 references
    advice strings
    0 references
    semi-feasible computation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references