Theory of Semi-Feasible Algorithms

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.

Contents

• P-Selectivity
• Nondeterrninistic Selectivity
• Bibliographic Notes

• Advice Strings and Circuits
• Advice for P-Selective Sets
• Advice for Nondeterministically Selective Sets
• Are There Unique Solutions for NP ?
• Bibliographic Notes

• Lowness Basics
• Lowness of P-Selective Sets
• Lowness of Nondeterministically Selective Sets
• Bibliographic Notes

• Can P-Selective Sets Be Hard for Complexity Classes ?
• Can P-Selective Sets Be Truth-Table-Hard for UP,Δ^p^2; , PSPACE, or EXP?
• Can P-Selective Sets Be Truth-Table-Hard or Turing-Hard for NP ?
• Can Nondeterministically Selective Sets Be NP-Hard or coNP-Hard ?
• Bibliographic Notes

• Connectives and Reductions
• Boolean Closures
• Reductions Under Which P-sel Is Closed Downward
• Self-Reducible Sets and Selectivity
• Reduction and Equivalence Classes
• Bibliographic Notes

• Generalizations of Selectivity
• P-Semi-Rankability: A Provable Refinement of P-Selectivity
• Associative P-Selectivity: A Potential Refinement of P-Selectivity
• Bibliographic Notes