Articles liés à Theory of Semi-Feasible Algorithms
Synopsis
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.
Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.
Résultats de recherche pour Theory of Semi-Feasible Algorithms
Image d'archives
Theory of Semi-Feasible Algorithms (EATCS Series: Monographs in Theoretical Computer Science)
Edité par
Springer, 2003
ISBN 10 : 3540422005
ISBN 13 : 9783540422006
Ancien ou d'occasion
Couverture rigide
Vendeur : killarneybooks, Inagh, CLARE, Irlande
Évaluation du vendeur 5 sur 5 étoiles
Hardcover. Etat : Near Fine. Hardcover, x + 148 pages, NOT ex-library. Clean and bright throughout with unmarked text, free of inscriptions and stamps, firmly bound. Boards show minor handling wear. Issued without a dust jacket. -- -- Theory of Semi-Feasible Algorithms is a comprehensive academic work within the field of theoretical computer science, focusing on the study of computational complexity, particularly the concept of semi-feasibility in algorithms. The book dives deeply into the properties and implications of semi-feasible sets, which are closely linked to selectivity in computational problems. It systematically analyses P-selective and nondeterministic selective sets, the role of advice in computational complexity, and the significance of lowness within complexity classes. The authors discuss P-selectivity as a measure of the ease with which membership in a set can be decided when given partial information, and how this concept extends to nondeterministic selectivity. The work explores the practical boundaries of these theoretical models, including advice strings, which provide additional information that can be used to solve problems, offering both upper and lower bounds for such advice in P-selective sets. Additionally, the book addresses key questions in complexity theory, such as whether P-selective sets can be hard for other complexity classes, like NP and PSPACE, or whether they can be truth-table or Turing-hard for these classes. An important component of the book is its investigation of the lowness properties of P-selective and nondeterministically selective sets, exploring how these sets can be placed within larger complexity hierarchies, such as the polynomial hierarchy, and their implications for computational power. The work also examines the closure properties of selectivity under various reductions and operations, including Boolean closures, self-reducibility, and equivalence classes, providing detailed insights into how these sets behave under specific computational transformations. Hemaspaandra and Torenvliet further generalize selectivity through weaker forms, such as multiselectivity and probabilistic selector functions, and introduce refinements to P-selectivity like P-semi-rankability and associative P-selectivity. These generalizations provide a more nuanced understanding of the relationship between selectivity and computational complexity. The monograph is aimed at researchers and students in theoretical computer science, particularly those interested in computational complexity theory, semi-feasibility, and algorithmic efficiency. It offers foundational concepts, advanced theorems, and rigorous proofs that contribute to the understanding of how semi-feasible algorithms fit into the broader landscape of computational complexity. -- "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.". N° de réf. du vendeur 010860
Acheter D'occasion
EUR 35,50
Expédition à EUR 33,70
Expédition depuis Irlande vers Etats-Unis
Expédition depuis Irlande vers Etats-Unis
Quantité disponible : 1 disponible(s)
Image fournie par le vendeur
Theory of Semi-Feasible Algorithms
Edité par
Springer, 2002
ISBN 10 : 3540422005
ISBN 13 : 9783540422006
Ancien ou d'occasion
Couverture rigide
Vendeur : -OnTimeBooks-, Phoenix, AZ, Etats-Unis
Évaluation du vendeur 5 sur 5 étoiles
Etat : very_good. Gently read. May have name of previous ownership, or ex-library edition. Binding tight; spine straight and smooth, with no creasing; covers clean and crisp. Minimal signs of handling or shelving. 100% GUARANTEE! Shipped with delivery confirmation, if you're not satisfied with purchase please return item! Ships USPS Media Mail. N° de réf. du vendeur OTV.3540422005.VG
Acheter D'occasion
EUR 77,86
Livraison gratuite
Expédition nationale : Etats-Unis
Expédition nationale : Etats-Unis
Quantité disponible : 1 disponible(s)
Image d'archives
Theory of Semi-Feasible Algorithms.
Edité par
Berlin Springer Verlag, 2002
ISBN 10 : 3540422005
ISBN 13 : 9783540422006
Ancien ou d'occasion
Couverture rigide
Vendeur : CSG Onlinebuch GMBH, Darmstadt, Allemagne
Évaluation du vendeur 5 sur 5 étoiles
Gebunden. Etat : Sehr gut. Gebraucht - Sehr gut Zustand: Sehr gut, X, 148 p. 6 illus. About this book 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. Written for scientists and graduate students. N° de réf. du vendeur 18183
Acheter D'occasion
EUR 29,71
Expédition à EUR 95
Expédition depuis Allemagne vers Etats-Unis
Expédition depuis Allemagne vers Etats-Unis
Quantité disponible : 1 disponible(s)
Image fournie par le vendeur
Theory of Semi-Feasible Algorithms
Edité par
Springer Berlin Heidelberg Okt 2002, 2002
ISBN 10 : 3540422005
ISBN 13 : 9783540422006
Neuf
Couverture rigide
Vendeur : BuchWeltWeit Ludwig Meier e.K., Bergisch Gladbach, Allemagne
Évaluation du vendeur 5 sur 5 étoiles
Buch. Etat : Neu. This item is printed on demand - it takes 3-4 days longer - Neuware -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. 164 pp. Englisch. N° de réf. du vendeur 9783540422006
Acheter neuf
EUR 106,99
Expédition à EUR 23
Expédition depuis Allemagne vers Etats-Unis
Expédition depuis Allemagne vers Etats-Unis
Quantité disponible : 2 disponible(s)
Image d'archives
Theory of Semi-Feasible Algorithms
Vendeur : GreatBookPrices, Columbia, MD, Etats-Unis
Évaluation du vendeur 5 sur 5 étoiles
Etat : New. N° de réf. du vendeur 1702905-n
Acheter neuf
EUR 134,75
Expédition à EUR 2,37
Expédition nationale : Etats-Unis
Expédition nationale : Etats-Unis
Quantité disponible : 15 disponible(s)
Image fournie par le vendeur
Theory of Semi-Feasible Algorithms
Edité par
Springer Berlin Heidelberg, 2002
ISBN 10 : 3540422005
ISBN 13 : 9783540422006
Neuf
Couverture rigide
Vendeur : moluna, Greven, Allemagne
Évaluation du vendeur 5 sur 5 étoiles
Gebunden. Etat : New. Dieser Artikel ist ein Print on Demand Artikel und wird nach Ihrer Bestellung fuer Sie gedruckt. A broad yet integrated study of Semi-Feasible AlgorithmsBrings the reader to the frontiers of current researchSelf-containedWith detailed derivation of resultsDoes not require difficult mathematicsCan be used in a course or for self-stud. N° de réf. du vendeur 4889676
Acheter neuf
EUR 92,27
Expédition à EUR 48,99
Expédition depuis Allemagne vers Etats-Unis
Expédition depuis Allemagne vers Etats-Unis
Quantité disponible : Plus de 20 disponibles
Image d'archives
Theory of Semi-Feasible Algorithms
Vendeur : Ria Christie Collections, Uxbridge, Royaume-Uni
Évaluation du vendeur 5 sur 5 étoiles
Etat : New. In English. N° de réf. du vendeur ria9783540422006_new
Acheter neuf
EUR 130,10
Expédition à EUR 13,36
Expédition depuis Royaume-Uni vers Etats-Unis
Expédition depuis Royaume-Uni vers Etats-Unis
Quantité disponible : Plus de 20 disponibles
Image fournie par le vendeur
Theory of Semi-Feasible Algorithms
Vendeur : AHA-BUCH GmbH, Einbeck, Allemagne
Évaluation du vendeur 5 sur 5 étoiles
Buch. Etat : Neu. Druck auf Anfrage Neuware - Printed after ordering - 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. N° de réf. du vendeur 9783540422006
Acheter neuf
EUR 124,85
Expédition à EUR 35
Expédition depuis Allemagne vers Etats-Unis
Expédition depuis Allemagne vers Etats-Unis
Quantité disponible : 1 disponible(s)
Image d'archives
Theory of Semi-Feasible Algorithms
Vendeur : Books Puddle, Woodside, NY, Etats-Unis
Évaluation du vendeur 4 sur 5 étoiles
Etat : New. pp. 164. N° de réf. du vendeur 262177947
Acheter neuf
EUR 157,64
Expédition à EUR 3,58
Expédition nationale : Etats-Unis
Expédition nationale : Etats-Unis
Quantité disponible : 4 disponible(s)
Image fournie par le vendeur
Theory of Semi-Feasible Algorithms
impression à la demandeVendeur : preigu, Osnabrück, Allemagne
Évaluation du vendeur 5 sur 5 étoiles
Buch. Etat : Neu. Theory of Semi-Feasible Algorithms | Lane A. Hemaspaandra (u. a.) | Buch | Monographs in Theoretical Computer Science. An EATCS Series | x | Englisch | 2002 | Springer | EAN 9783540422006 | Verantwortliche Person für die EU: Springer Verlag GmbH, Tiergartenstr. 17, 69121 Heidelberg, juergen[dot]hartmann[at]springer[dot]com | Anbieter: preigu Print on Demand. N° de réf. du vendeur 103864634
Acheter neuf
EUR 95,70
Expédition à EUR 70
Expédition depuis Allemagne vers Etats-Unis
Expédition depuis Allemagne vers Etats-Unis
Quantité disponible : 5 disponible(s)