Информатика и вычислительная техника
  • формат pdf
  • размер 2.31 МБ
  • добавлен 20 сентября 2011 г.
Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms
Издательство Springer, 2005, -306 pp.

Complexity theory – is it a discipline for theoreticians who have no conce for the real world or a central topic of mode 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 will explore the borders of what is algorithmically possible with reasonable resources. Since this text is also especially directed toward those who do not wish to make complexity theory their specialty, results that do not (yet) have a connection to algorithmic applications will be omitted.
The areas of complexity theory on the one hand and of the design and analysis of efficient algorithms on the other look at algorithmic problems from two opposing perspectives. An efficient algorithm can be directly applied to solve a problem and is itself a proof of the efficient solvability of the problem. In contrast, in complexity theory the goal is to prove that difficult problems cannot be solved with modest resources. Bearers of bad news are seldom welcome, and so it is that the results of complexity theory are more difficult to communicate than a better algorithm for an important problem. Those who do complexity theory are often asked such questions as
Why are you pleased with a proof that a problem is algorithmically difficult? It would be better if it had an efficient algorithmic solution.
What good are these results? For my particular applied problem I need an algorithmic solution. Now what do I do?
Naturally, it would be preferable if a problem proved to be efficiently algorithmically solvable. But whether or not this is the case is not up to us. Once we have agreed upon the rules of the game (roughly: computers, but more about that later), every problem has a well-defined algorithmic complexity. Complexity theory and algorithm theory are both striving to estimate this lgorithmic complexity and so to discover the truth. In this sense, the joy over a proof that a problem is not efficiently solvable is, just like the joy over the design of an efficient algorithm, the joy of finding out more about the true algorithmic complexity.
Of course, our reaction to the discovery of truths does depend on whether hopes were fulfilled or fears confirmed. What are the consequences when we find out that the problem we are investigating is not efficiently solvable? First, there is the obvious and very practical consequence that we can with good reason abandon the search for an efficient algorithm. We need no longer waste our time with attempts to obtain an unreachable goal. We are familiar with this from other sciences as well. Reasonable people no longer build perpetual motion machines, and they no longer try to construct from a circle, using only straight edge and compass, a square with the same area (the proverbial quadrature of the circle). In general, however, people have a hard time with impossibility results. This can be seen in the large number of suggested designs for perpetual motion machines and the large number of attempts to square a circle that are still being made.
Once we have understood that we must accept negative results as well as positive results, and that they save us unnecessary work, we are left with the question of what to do. In the end, we are dealing with an algorithmic problem the solution to which is important for some particular application. Fortunately, problems in most applications are not unalterably determined. It is often tempting to formulate a problem in a very general form and to place very strict demands on the quality of the solution. If such a general formulation has an efficient solution, great. But when this is not the case, we can often specialize the problem (graphs that model street systems will have low degree because there is a limit on the number of streets that can meet at a single intersection), or perhaps a weaker form of solution will suffice (almost optimal may be good enough). In this way we come up with new problems which are perhaps efficiently algorithmically solvable. And so impossibility proofs (negative results) help us find the problems that are (perhaps just barely) efficiently solvable.
So complexity theory and the design and analysis of efficient algorithms are the two areas of computer science which together fathom the borders between what can and cannot be done algorithmically with realistic resource requirements. There is, of course, a good deal of cross-pollination between the two areas. Often attempts to prove the impossibility of an efficient solution to a problem have so illuminated the structure of the problem that efficient algorithms have been the result. On the other hand, failed attempts to design an efficient algorithm often reveal just where the difficulty of a particular problem lies. This can lead to ideas for proving the difficulty of the problem. It is very often the case that one begins with a false conjecture about the degree of difficulty of a problem, so we can expect to encounter startling results in our study of the complexity of problems.
As a result of this introductory discussion we maintain that The goal of complexity theory is to prove for important problems that their solutions require certain minimum resources. The results of complexity theory have specific implications for the development of algorithms for practical applications.

Introduction
Algorithmic Problems & Their Complexity
Fundamental Complexity Classes
Reductions – Algorithmic Relationships Between Problems
The Theory of NP-Completeness
NP-complete and NP-equivalent Problems
The Complexity Analysis of Problems
The Complexity of Approximation Problems – Classical Results
The Complexity of Black Box Problems
Additional Complexity Classes
Interactive Proofs
The PCP Theorem and the Complexity of Approximation Problems
Further Topics From Classical Complexity Theory
The Complexity of Non-uniform Problems
Communication Complexity
The Complexity of Boolean Functions
Final Comments
Читать онлайн
Похожие разделы
Смотрите также

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...

Atallah M.J., Blanton M. Algorithms and Theory of Computation Handbook: Special Topics and Techniques

  • формат pdf
  • размер 10.74 МБ
  • добавлен 22 августа 2011 г.
Chapman and Hall/CRC, 2009. - 950 pages. Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. Along with updating and revising many of the existing chapters, this second edition contains mo...

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...

Flum J., Grohe M. Parameterized Complexity Theory

  • формат pdf
  • размер 3.68 МБ
  • добавлен 08 февраля 2012 г.
Издательство 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 Stearns in the early 1960s, to measure the required amount of the resource as a...

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.

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...