Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2011 | Buch

Preliminaries Kapitel lesen Erstes Kapitel lesen

Computability and Complexity Theory

verfasst von: Steven Homer, Alan L. Selman

Verlag: Springer US

Buchreihe : Texts in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations. Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable. Substantial new content in this edition includes:

a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp─Lipton.a chapter studying properties of the fundamental probabilistic complexity classesa study of the alternating Turing machine and uniform circuit classes. an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Todaa thorough treatment of the proof that IP is identical to PSPACE

With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential and practical learning tool.

Topics and features:

Concise, focused materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes Contains information that otherwise exists only in research literature and presents it in a unified, simplified mannerProvides key mathematical background information, including sections on logic and number theory and algebra Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes

Inhaltsverzeichnis

Frontmatter
Chapter 1. Preliminaries
Abstract
We begin with a limited number of mathematical notions that a student should know before beginning with this text. This chapter is short because we assume some earlier study of data structures and discrete mathematics.
Steven Homer, Alan L. Selman
Chapter 2. Introduction to Computability
Abstract
This subject is primarily concerned with the limitations of computing. As one of the highlights of this study, we will learn several specific problems that computers cannot solve.
Steven Homer, Alan L. Selman
Chapter 3. Undecidability
Abstract
A decision problem is a general question to be answered, usually possessing several parameters, or free variables, whose values are left unspecified. An instance of a problem is obtained by specifying particular values for all of the problem parameters.
Steven Homer, Alan L. Selman
Chapter 4. Introduction to Complexity Theory
Abstract
The remaining chapters of this book are concerned with complexity theory. The goal of complexity theory is to provide mechanisms for classifying combinatorial problems and measuring the computational resources necessary to solve them. Complexity theory provides an explanation of why certain problems have no practical solutions and provides a way of anticipating difficulties involved in solving problems of certain types. The classification is quantitative and is intended to investigate what resources are necessary (lower bounds) and what resources are sufficient (upper bounds) to solve various problems.
Steven Homer, Alan L. Selman
Chapter 5. Basic Results of Complexity Theory
Abstract
We begin our study of complexity theory by examining the fundamental properties of complexity classes. These results apply to all complexity classes and show that the definitions of these classes are invariant under small changes in the time or space bounds of the Turing machines that define them. We will prove general relationships between time- and space-bounded complexity classes. These consist of inclusions between some classes and separations of other classes. Then we will apply the methods and results of these general relationships to important specific cases in order to establish relationships between the central standard complexity classes we defined in the previous chapter. In order to begin this study we need to understand some simple assertions that involve the behavior of functions at limits, so let’s review these now.
Steven Homer, Alan L. Selman
Chapter 6. Nondeterminism and NP-Completeness
Abstract
Several different additions to the basic deterministic Turing machine model are often considered. These additions add computational power to the model and so allow us to compute certain problems more efficiently. Often these are important problems with seemingly no efficient solution in the basic model. The question then becomes whether the efficiency the additional power provides is really due to the new model or whether the added efficiency could have been attained without the additional resources.
Steven Homer, Alan L. Selman
Chapter 7. Relative Computability
Abstract
In this chapter we expand more broadly on the idea of using a subroutine for one problem in order to efficiently solve another problem. By doing so, we make precise the notion that the complexity of a problem B is related to the complexity of A – that there is an algorithm to efficiently accept Brelative to an algorithm to efficiently decide A. As in Sect.  3.​9, this should mean that an acceptor for B can be written as a program that contains subroutine calls of the form “x ∈ A,” which returns True if the Boolean test is true and returns False otherwise. Recall that the algorithm for accepting B is called a reduction procedure and the set A is called an oracle. The reduction procedure is polynomial time-bounded if the algorithm runs in polynomial time when we stipulate that only one unit of time is to be charged for the execution of each subroutine call. Placing faith in our modified Church’s thesis and in Cobham’s thesis, these ideas, once again, are made precise via the oracle Turing machine.
Steven Homer, Alan L. Selman
Chapter 8. Nonuniform Complexity
Abstract
In this chapter we introduce and study Boolean circuits. Since real computers are built from electronic devices, digital circuits, this is reason enough to consider their complexity. The circuits that we consider here are idealizations of digital circuits just as the Turing machine is an idealization of real digital computers.
Steven Homer, Alan L. Selman
Chapter 9. Parallelism
Abstract
We consider the theory of synchronous highly parallel computations. VLSI chip technology is making it possible to connect together large numbers of processors to operate together synchronously. The question, of course, is what can be done with the result.
Steven Homer, Alan L. Selman
Chapter 10. Probabilistic Complexity Classes
Abstract
In this chapter we study the benefits of adding randomness to computations. We treat randomness as a resource. Probabilistic algorithms allow computations to depend on the outcomes of an ideal random generator (i.e., on unbiased coin tosses). They can be classified by classifying the languages they are defined to accept. Important computational problems that seem to be infeasible by ordinary deterministic computations have efficient solutions using probabilistic algorithms. Such algorithms can be easily implemented, and fast and reliable solutions to otherwise difficult problems are then possible. There is a cost to this added efficiency, however, in that probabilistic algorithms do sometimes make errors.
Steven Homer, Alan L. Selman
Chapter 11. Introduction to Counting Classes
Abstract
Our interest in nondeterministic polynomial time-bounded Turing machines has been concerned primarily with the question of whether, given an input x, there exists at least one accepting computation. However, this is not entirely so, for the definition of PP is that the majority of computations are accepting. Now we will be interested in the following classes, which use counting explicitly in their definitions.
Steven Homer, Alan L. Selman
Chapter 12. Interactive Proof Systems
Abstract
Recall the characterization of NP as the class of languages A having a polynomial-time verifier (Corollary 6.1). The verifier is capable of checking that a string is a short (polynomial-length) proof that an element is in the NP set A. Furthermore the verifier works in polynomial time. We do not put any restriction on how the verifier obtains the proof itself, it is sufficient that the proof exists. For example, the proof might be provided by a powerful prover with unrestricted computational power.
Steven Homer, Alan L. Selman
Backmatter
Metadaten
Titel
Computability and Complexity Theory
verfasst von
Steven Homer
Alan L. Selman
Copyright-Jahr
2011
Verlag
Springer US
Electronic ISBN
978-1-4614-0682-2
Print ISBN
978-1-4614-0681-5
DOI
https://doi.org/10.1007/978-1-4614-0682-2

Premium Partner

    Bildnachweise