Информатика и вычислительная техника
  • формат pdf
  • размер 3.68 МБ
  • добавлен 08 февраля 2012 г.
Flum J., Grohe M. Parameterized Complexity Theory
Издательство Springer, 2006, -494 pp.

Parameterized complexity theory provides a framework for a refined analysis of hard algorithmic problems.
Classical complexity theory analyzes and classifies problems by the amount of a resource, usually time or space, that is required by algorithms solving them. It was a fundamental idea, going back to the work of Hartmanis and Steas in the early 1960s, to measure the required amount of the resource as a function of the size of the input. This has led to a manageable variety of complexity classes and a clean-cut theory of intractability. However, measuring complexity only in terms of the input size means ignoring any structural information about the input instances in the resulting complexity theory. Sometimes, this makes problems appear harder than they typically are. Parameterized complexity theory takes a step backwards and measures complexity not only in terms of the input size, but in addition in terms of a parameter, which is a numerical value that may depend on the input in an arbitrary way. The main intention is to address complexity issues in situations where we know that the parameter is comparatively small.
Consider, for example, the problem of evaluating a database query. Its input has two parts, a database and the query. Observe that these two parts will usually differ in size quite significantly; the database will be much larger than the query. A natural parameter for a parameterized complexity analysis of this problem is the size of the query. As a more theoretically motivated example, consider approximation schemes for optimization problems. Their input consists of a problem instance and an error bound ?. A natural parameter is 1/?. If we can accept an error of 5% in an approximation, we have a parameter value 1/?=20 for our approximation scheme. Typical parameters for many algorithmic problems on graphs are the tree width or the maximum degree of the input graph. Numerous other examples of naturally parameterized problems can be found in other application areas such as automated verification, artificial intelligence, or computational biology. The central notion of parameterized complexity theory is fixed-parameter tractability. It relaxes the classical notion of tractability, polynomial time solvability, by admitting algorithms whose nonpolynomial behavior is restricted by the parameter.
Of course, algorithms have always been analyzed and optimized in terms of many different input parameters, and no complexity theory was needed to do this. The main contribution of the theory is to provide a framework for establishing the intractability of certain problems. In the absence of techniques for actually proving lower bounds for natural problems, the main goal of such a theory is to classify problems into complexity classes by means of suitable reductions. Since the parameterized theory is two-dimensional, depending not only on the input size but also on the parameter, it is not surprising that it leads to a much larger variety of complexity classes and to more complicated reductions than the classical, one-dimensional complexity theory.
Besides providing a theory of intractability, parameterized complexity theory also provides a theory of fixed-parameter tractability that had significant impact on the design of algorithms. By consciously studying parameterized problems from different areas, researchers were able to devise new general algorithmic techniques for solving parameterized problems efficiently for small parameter values and to put existing algorithmic ideas into a larger context. Some of these general techniques are known as the method of bounded search trees, keelization, color coding, and dynamic programming on tree decompositions.
An aspect of parameterized complexity theory that has gained importance more recently is its close connection with an area sometimes referred to as exact exponential worst-case complexity analysis. This area is conceed with exact algorithms1 for hard algorithmic problems that are better than the trivial brute-force algorithms and corresponding (exponential) lower bounds for the running time of such algorithms. The role of the parameter in this context is to capture more precisely the main source of the (exponential) complexity of a problem. For example, the complexity of the satisfiability problem for formulas of propositional logic is better analyzed in terms of the number of variables of the input formula than in terms of its size.
Parameterized complexity theory is a fairly new branch of complexity theory. It was developed by Downey and Fellows in a series of ground breaking articles in the early 1990s. In these articles, Downey and Fellows defined the notion of fixed-parameter tractability, came up with suitable notions of reductions, defined the most important complexity classes, and proved a number of fundamental completeness results. Since then, numerous other researchers have contributed to the theory. Downey and Fellows’ 1999 monograph [83] gives a fairly complete picture of the theory then. The development has not slowed down since then, quite to the contrary. However, we feel that the field has matured to a degree that it deserves a comprehensive state-of-the art introduction, which we hope to provide by this book.

Fixed-Parameter Tractability
Reductions and Parameterized Intractability
TheClassW[P]
Logic and Complexity
Two Fundamental Hierarchies
The First Level of the Hierarchies
TheW-Hierarchy
TheA-Hierarchy
Keelization and Linear Programming Techniques
The Automata-Theoretic Approach
Tree Width
Planarity and Bounded Local Tree Width
Homomorphisms and Embeddings
Parameterized Counting Problems
Bounded Fixed-Parameter Tractability
Subexponential Fixed-Parameter Tractability
Background from Complexity Theory
Похожие разделы
Смотрите также

Atallah M.J., Blanton M. (eds.) Algorithms and Theory of Computation Handbook. General Concepts and Techniques

Справочник
  • формат pdf
  • размер 8.46 МБ
  • добавлен 30 января 2012 г.
Издательство Chapman&Hall/CRC Press, 2010, -990 pp. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of al...

Bogdanov A., Trevisan L. Average-Case Complexity

  • формат pdf
  • размер 737.3 КБ
  • добавлен 05 октября 2011 г.
Computing Research Repository, 2008, -81 pp. We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect...

Goldreich O. Computational Complexity. A Conceptual Perspective

  • формат pdf
  • размер 3.3 МБ
  • добавлен 31 октября 2011 г.
Издательство Cambridge University Press, 2008, -632 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Goldreich O. P, NP, and NP-Completeness. The Basics of Computational Complexity

  • формат pdf
  • размер 1.11 МБ
  • добавлен 31 октября 2011 г.
Издательство Cambridge University Press, 2010, -216 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Hopcroft John E., Motwani Rajeev, Ullman Jeffrey D. Introduction to Automata Theory, Languages, and Computation (2nd Edition)

  • формат djvu
  • размер 8.64 МБ
  • добавлен 29 марта 2011 г.
This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications.

Kozen D.C. Theory of Computation

  • формат pdf
  • размер 2.75 МБ
  • добавлен 08 декабря 2011 г.
Издательство Springer, 2006, -405 pp. The course serves a dual purpose: to cover core material in the foundations of computing for graduate students in computer science preparing for their PhD qualifying exams, and to provide an introduction to some more advanced topics in the theory of computational complexity for those intending to pursue further study in the area. The course is thus a mixture of core and advanced material. Most of the course...

Lee T., Shraibman A. Lower Bounds in Communication Complexity: A Survey

  • формат pdf
  • размер 943.48 КБ
  • добавлен 07 октября 2011 г.
Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -127 pp. We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as rank, or the trace norm that serves as a lower bound to the unde...

Sipser Michael. Introduction to The Theory of Computation, Second Edition

  • формат djvu
  • размер 6.57 МБ
  • добавлен 30 октября 2009 г.
Книга профессора прикладной математики из Массачу?сетского технологи?ческого институ?та. Русского преревода, к сожалению, не существует (или я не нашел). Очень полезная книжка. В Маи по ней читаются лекции по Сппо. Michael Sipser Welcome! You are about to embark on the study of a fascinating and important subject. the theory of computation. It comprises the fundamental mathematical proper. ties of computer hardware, software, and certain applic...

Van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A. Algorithms and Complexity

  • формат djvu
  • размер 12.2 МБ
  • добавлен 11 мая 2011 г.
Издательсто Elsiever/MIT Press, 1990, -1010 pp. Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений Machine Models and Simulations A Catalog of Complexity Classes Machine-Independent Complexity Theory Kolmogorov Complexity and its Applications Data Structures Computational Geometry Algorithmic Motion Planning in Robotics Average-Case Analysis of Algorithms and Data Structures Graph Algorithms Algorithms in Number Theory...

Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

  • формат pdf
  • размер 2.31 МБ
  • добавлен 20 сентября 2011 г.
Издательство Springer, 2005, -306 pp. Complexity theory – is it a discipline for theoreticians who have no concern for the real world or a central topic of modern computer science? In this introductory text, complexity theory is presented as an active area of computer science with results that have implications for the development and use of algorithms. Our study will lead to insights into the structure of important optimization problems and wil...