Информатика и вычислительная техника
  • формат pdf
  • размер 2.75 МБ
  • добавлен 08 декабря 2011 г.
Kozen D.C. Theory of Computation
Издательство 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 is conceed with computational complexity, or the classification of computational problems in terms of their inherent complexity. This usually refers to time or space usage on a particular computational model, but may include other complexity measures as well, such as randomness, number of alteations, or circuit size or depth. We include a rigorous treatment of computational models, including deterministic, nondeterministic, and alteating Turing machines, circuits, probabilistic machines, interactive proof systems, automata on infinite objects, and various logical formalisms. Also included are various approximation and inapproximation results and some lower bounds. According to most treatments, the complexity universe stops at polynomial space, but we also look at higher levels of complexity all the way up through the primitive recursive functions, partial recursive functions, and the arithmetic and analytic hierarchies.

The Complexity of Computations
Time and Space Complexity Classes and Savitch’s Theorem
Separation Results
The Immerman–Szelepcs?enyi Theorem
Logspace Computability
The Circuit Value Problem
The Knaster–Tarski Theorem
Alteation
Problems Complete for PSPACE
The Polynomial-Time Hierarchy
More on the Polynomial-Time Hierarchy
Parallel Complexity
Relation of NC to Time-Space Classes
Probabilistic Complexity
BPP ? ???2
Chinese Remaindering
Complexity of Primality Testing
Berlekamp’s Algorithm
Interactive Proofs
PSPACE ? IP
IP ? PSPACE
Probabilistically Checkable Proofs
NP ? PCP(n3,1)
More on PCP
A Crash Course in Logic
Complexity of Decidable Theories
Complexity of the Theory of Real Addition
Lower Bound for the Theory of Real Addition
Lower Bound for Integer Addition
Automata on Infinite Strings and S1S
Determinization of ?-Automata
Safra’s Construction
Relativized Complexity
Nonexistence of Sparse Complete Sets
Unique Satisfiability
Toda’s Theorem
Circuit Lower Bounds and Relativized PSPACE=PH
Lower Bounds for Constant Depth Circuits
The Switching Lemma
Tail Bounds
The Gap Theorem and Other Pathology
Partial Recursive Functions and G?odel Numberings
Applications of the Recursion Theorem
Abstract Complexity
The Arithmetic Hierarchy
Complete Problems in the Arithmetic Hierarchy
Post’s Problem
The Friedberg–Muchnik Theorem
The Analytic Hierarchy
Kleene’s Theorem
Fair Termination and Harel’s Theorem
Exercises
Hints and Solutions
Читать онлайн
Похожие разделы
Смотрите также

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

Brassard G., Bratley P. Algorithmics: Theory and Practice

  • формат pdf
  • размер 3.85 МБ
  • добавлен 03 января 2011 г.
Prentice Hall, 1988. - 302 pages. From the Preface of the book: Our book is neither a programming manual nor an account of the proper use of data structures. Still less is it a "cookbook" containing a long catalogue of programs ready to be used directly on a machine to solve certain specific problems, but giving at best a vague idea of the principles involved in their design. On the contrary, the aim of our book is to give the reader some basic...

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.

Lipton R.J. The P=NP Question and G?del’s Lost Letter

  • формат pdf
  • размер 2.34 МБ
  • добавлен 07 октября 2011 г.
Издательство Springer, 2010, -222 pp. Does P=NP?. In just five symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he first wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of computation, it is a very hard problem, and its resolution will have potentially tremendou...

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