The Complexity Theory Companion | springerprofessional.de

Springer Professional

nach oben

2002 | Buch

Kapitel lesen Erstes Kapitel lesen

The Complexity Theory Companion

verfasst von: Prof. Dr. Lane A. Hemaspaandra, Prof. Dr. Mitsunori Ogihara

Verlag: Springer Berlin Heidelberg

Buchreihe : Texts in Theoretical Computer Science. An EATCS Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

Invitation Invitation Secret Secret 1 1 Algorithms Algorithms are are at at the the heart heart of of complexity complexity theory. theory. That That is is the the dark dark secret secret of of complexity complexity theory. theory. It It is is recognized recognized by by complex complex ity ity theorists, theorists, but but would would be be literally literally incredible incredible to to most most others. others. In In this this book, book, we we hope hope to to make make this this secret secret credible. credible. In In fact, fact, the the real real secret secret is is even even more more dramatic. dramatic. Secret Secret 2 2 Simple Simple algorithms algorithms are are at at the the heart heart of of complexity complexity theory. theory. A A corollary corollary of of Secret Secret 2 2 is is that that every every practitioner practitioner of of computer computer science science or or stu stu dent dent of of computer computer science science already already possesses possesses the the ability ability required required to to understand, understand, enjoy, enjoy, and and employ employ complexity complexity theory. theory.

Anzeige

Inhaltsverzeichnis

Frontmatter

1. The Self-Reducibility Technique

Abstract

A set S is sparse if it contains at most polynomially many elements at each length, i.e.,

$$ \left( {\exists \;polynomial\;p} \right)\left( {\forall n} \right)\left[ {||\{ x|x \in S \wedge |x| = n\} || \le p\left( n \right)} \right] $$

(1.1)

.

Lane A. Hemaspaandra, Mitsunori Ogihara

2. The One-Way Function Technique

Abstract

No proven one-way functions are known. Not even one. Nonetheless, one-way functions play a central role in complexity theory and cryptography. In complexity theory, one-way functions have been used in the (to date unsuccessful) attempts to show that there exist two NP-complete sets that are not essentially the same set in disguise (i.e., that are not polynomial-time isomorphic). In average-case and worst-case cryptography, one-way functions have been used as key components in the construction of cryptographic protocols.

Lane A. Hemaspaandra, Mitsunori Ogihara

3. The Tournament Divide and Conquer Technique

Abstract

If computer science were a country rather than a field, one can well imagine that its motto would be “Divide and Conquer,” which might have edged out “In Polynomial Time We Trust.” Indeed, divide and conquer techniques accompany the computer scientist from the introduction to binary search through the mastery of cutting-edge algorithmic techniques. However, computer scientists do not own the franchise. Divide and conquer techniques are useful in many fields.

Lane A. Hemaspaandra, Mitsunori Ogihara

4. The Isolation Technique

Abstract

Counting is cumbersome and sometimes painful. Studying NP would indeed be far simpler if all NP languages were recognized by NP machines having at most one accepting computation path, that is, if NP = UP. The question of whether NP = UP is a nagging open issue in complexity theory. There is evidence that standard proof techniques can settle this question neither affirmatively nor negatively. However, surprisingly, with the aid of randomness we will relate NP to the problem of detecting unique solutions. In particular, we can reduce, with high probability, the entire collection of accepting computation paths of an NP machine to a single path, provided that initially there is at least one accepting computation path. We call such a reduction method an isolation technique.

Lane A. Hemaspaandra, Mitsunori Ogihara

5. The Witness Reduction Technique

Abstract

Don’t you feel cheated when someone tells you the answer to a question before you’ve had a chance to ponder the issue for yourself? Sure you do, but this happens all the time. For example, if you are reading this book, you probably already know the beautiful theory of NP-completeness that was built by Cook, Levin, and Karp a few decades ago. So you already know the standard, striking, subtle answer the field has built to Pause to Ponder 5.1, namely, “We don’t know whether or not SAT is in P, but we do know that SAT is in P if and only if all of the following thousand problems are in P, and we also know that SAT is in P if and only if at least one of the following (same) thousand problems is in P.” (For reasons of space, we omit the list of one thousand NPcomplete problems.) Basically, your ability to consider Pause to Ponder 5.1 as a fresh problem has been pretty thoroughly tainted.

Lane A. Hemaspaandra, Mitsunori Ogihara

6. The Polynomial Interpolation Technique

Abstract

A standard view of mathematical statements is that they should be accompanied by succinctly written, easily verifiable certificates. To wit, open one of your favorite mathematics or theoretical computer science textbooks (if you have one; if not, perhaps the present text will become your favorite). You’ll see that all the formal statements there are accompanied by strings of text called proofs, which the author believes to be easily verifiable by anyone with enough background.

Lane A. Hemaspaandra, Mitsunori Ogihara

7. The Nonsolvable Group Technique

Abstract

Bounded-width branching programs offer interesting connections between complexity classes and algebraic structures. Let k ≥ 2 and n ≥ 1 be integers. A width-k branching program over n-bit inputs prescribes manipulation of a pebble placed on a track of k squares. First the pebble is place d on square 1. Then a sequence of instructions is executed. Each instruction is simple: it tells you to examine an input bit and then move the pebble to another (possibly the same) square, where to which square the pebble will be moved depends on the examined bit, the current location of the pebble, and the step of the computation. The program accepts the input if and only if the pebble is not on square 1 at the end.

Lane A. Hemaspaandra, Mitsunori Ogihara

8. The Random Restriction Technique

Abstract

Oracle construction is a major tool for studying questions about complexity classes. Suppose we find an oracle relative to which a complexity-theoretic property Q holds and another oracle relative to which Q does not hold. Then we can conclude that settling the question of whether Q holds without assumption is very tough, in the sense that proof techniques that can be relativized, such as those based on Turing-machine computation, cannot on their own successfully resolve whether Q holds.

Lane A. Hemaspaandra, Mitsunori Ogihara

9. The Polynomial Technique

Abstract

One way of understanding the computational flexibility inherent in a complexity class, C, is to determine the closure properties the class possesses and lacks. Under which operations is the class closed: complementation? union? intersection? symmetric difference? And under which reducibilities is the class closed? That is, for a class C, we may naturally ask: For which reductions ≤_r, does it hold that R _r (C) ⊆ C? Answering such a question can give insight not just into the computational flexibility of a class but also into the identity of the class. If C is closed? under some operation and D is not, then C D. And, more typ ic ally in the world of complexity, if C is closed under some operation and D has to date defeated dall effort s to prove it closed under that operation, then we may take this as one piece of evidence that may suggest that the classes may differ.

Lane A. Hemaspaandra, Mitsunori Ogihara

A. A Rogues’ Gallery of Complexity Classes

Abstract

To the computer scientist, structure is meaning. Seeking to understand nature’s diverse problems with man’s humble resources, we simplify our task by grouping similarly structured problems. The resulting complexity classes, such as P, NP, and PSPACE, are simply families of problems that can be solved with a certain underlying computational power. The range of interesting computational powers is broad—deterministic, nondeterministic, probabilistic, unique, table lookup, etc.—and a suitably rich palette has been developed to reflect these powers—P, NP, PP, UP, P/poly, etc. These classes can themselves be studied in terms of their internal structure and behavior. This chapter briefly reviews the definitions, meanings, and histories of the central complexity classes covered in this book.

Lane A. Hemaspaandra, Mitsunori Ogihara

B. A Rogues’ Gallery of Reductions

Abstract

If one can solve problem A using a black box that solves problem B, one can reasonably say that problem A is “not much harder than” problem B, the degree of the “not much” being linked to how powerful and extensive the use of B is. Thus, reductions provide a means of classifying the relative hardness of sets. If A reduces to B and B reduces to A, then we can reasonably say that A and B are of “about the same” hardness. Of course, the closeness of the relationship between A and B will again depend on how powerful the reduction is. The more computationally weak the reduction is, the stronger the claim we can make about the similarity of hardness of A and B. Over the years, a rich collection of reductions has been developed to aid in classifying the relative hardness of sets. In this chapter, we define the key reductions, mention some standard notational shorthands, and then present some comments about reductions and their relative powers. We also discuss a centrally important reduction, Cook’s reduction, which is the reduction that proves that SAT is NP-complete.

Lane A. Hemaspaandra, Mitsunori Ogihara

Backmatter

Titel: The Complexity Theory Companion
verfasst von: Prof. Dr. Lane A. Hemaspaandra
Prof. Dr. Mitsunori Ogihara
Copyright-Jahr: 2002
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-04880-1
Print ISBN: 978-3-642-08684-7
DOI: https://doi.org/10.1007/978-3-662-04880-1

Weitere Formate
Fachgebiete
Bücher
Zeitschriften
Themenseiten
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024