Exact Exponential Algorithms
Today most computer scientists believe that NP-hard problems cannot be solved by polynomial-time algorithms. From the polynomial-time perspective, all NP-complete problems are equivalent but their exponential-time properties vary widely. Why do some NP-ha
- PDF / 356,442 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 263 Views
Advisory Board: G. Ausiello M. Broy C.S. Calude A. Condon D. Harel J. Hartmanis T. Henzinger T. Leighton M. Nivat C. Papadimitriou D. Scott
For further volumes: http://www.springer.com/series/3214
Fedor V. Fomin · Dieter Kratsch
Exact Exponential Algorithms
123
Prof. Dr. Fedor V. Fomin University of Bergen Inst. Informatics PO Box 7800 5020 Bergen Norway [email protected]
Series Editors Prof. Dr. Wilfried Brauer Institut f¨ur Informatik der TUM Boltzmannstr. 3 85748 Garching, Germany [email protected]
Prof. Dr. Grzegorz Rozenberg Leiden Institute of Advanced Computer Science University of Leiden Niels Bohrweg 1 2333 CA Leiden, The Netherlands [email protected]
Prof. Dieter Kratsch Universit´e Paul Verlaine - Metz LITA, UFR MIM D´ept. Informatique Ile du Saulcy 57045 Cedex 1 France [email protected]
Prof. Dr. Juraj Hromkoviˇc ETH Zentrum Department of Computer Science Swiss Federal Institute of Technology 8092 Z¨urich, Switzerland [email protected] Prof. Dr. Arto Salomaa Turku Centre of Computer Science Lemmink¨aisenkatu 14 A 20520 Turku, Finland [email protected]
ISSN 1862-4499 ISBN 978-3-642-16532-0 e-ISBN 978-3-642-16533-7 DOI 10.1007/978-3-642-16533-7 Springer Heidelberg Dordrecht London New York ACM Codes: F.2, G.1, G.2 c Springer-Verlag Berlin Heidelberg 2010 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: KuenkelLopka GmbH, Heidelberg Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
For a long time computer scientists have distinguished between fast and slow algorithms. Fast (or good) algorithms are the algorithms that run in polynomial time, which means that the number of steps required for the algorithm to solve a problem is bounded by some polynomial in the length of the input. All other algorithms are slow (or bad). The running time of slow algorithms is usually exponential. This book is about bad algorithms. There are several reasons why we are interested in exponential time algorithms. Most of us believe that there are many natural problems which cannot be solved by polynomial time algorithms. The most famous and oldest family of hard problems is the family of NP-complete problems. Most likely there are no
Data Loading...
