Theory of semi-feasible algorithms (Q5959347)

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.