Overview
An Invitation to the Dance It is an underappreciated fact that sets may have various types of complex ity, and not all types are in harmony with each other. The primary goal of this book is to unify and make more widely accessible a vibrant stream of research-the theory of semi-feasible computation-that perfectly showcases the richness of, and contrasts between, the central types of complexity. The semi-feasible sets, which are most commonly referred to as the P selective sets, are those sets L for which there is a deterministic polynornial time algorithm that, when given as input any two strings of which at least one belongs to L, will output one of them that is in L. The reason we saythat the semi-feasible sets showcase the contrasts among types of complexity is that it is well-known that many semi-feasible sets have no recursive algorithms (thus their time complexitycannot be upper-bounded by standard time-complexity classes), yet all semi-feasible sets are simple in a wide range of other natural senses. In particular, the semi-feasible sets have small circuits, they are in the extended low hierarchy, and they cannot be NP-complete unless P = NP. The semi-feasible sets are fascinating for many reasons. First, as men tioned above, they showcase the fact that mere deterministic time complex ity is not the only potential type of complexity in the world of computation.
Full Product Details
Author: Lane A. Hemaspaandra ,
Leen Torenvliet
Publisher: Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition: Softcover reprint of the original 1st ed. 2003
Dimensions:
Width: 15.50cm
, Height: 0.80cm
, Length: 23.50cm
Weight: 0.454kg
ISBN: 9783642075810
ISBN 10: 3642075819
Pages: 150
Publication Date: 09 December 2010
Audience:
Professional and scholarly
,
Professional and scholarly
,
Professional & Vocational
,
Postgraduate, Research & Scholarly
Format: Paperback
Publisher's Status: Active
Availability: In Print
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.
Reviews
From the reviews: This book focuses mainly on the complexity of P-selective sets ! . a course from this text would require a highly-motivated instructor who can give the intuitive ideas leaving the details to the book. The book would also serve as a reasonable reference for those doing research in this area. (Lance Fortnow, SIGACT News, Vol. 35 (2), 2004)
"From the reviews: ""This book focuses mainly on the complexity of P-selective sets … . a course from this text would require a highly-motivated instructor who can give the intuitive ideas leaving the details to the book. The book would also serve as a reasonable reference for those doing research in this area."" (Lance Fortnow, SIGACT News, Vol. 35 (2), 2004)"
