Theory of Semi-Feasible Algorithms

Lane A. Hemaspaandra, Leen Torenvliet

158 pages, parution le 12/11/2002

Ajouter à une liste

Indisponible

Résumé

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

1. Introduction to Semi-Feasible Computation

P-Selectivity
Nondeterrninistic Selectivity
Bibliographic Notes

2. Advice

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

3. Lowness

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

4. Hardness for Complexity Classes

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

5. Closures

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

6. Generalizations and Related Notions

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

A. Definitions of Reductions and Complexity Classes, and Notation List

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Lane A. Hemaspaandra, Leen Torenvliet
Parution	12/11/2002
Nb. de pages	158
Format	16 x 24
Couverture	Relié
Poids	360g
Intérieur	Noir et Blanc
EAN13	9783540422006