Vor Ort
Merkzettel Warenkorb
Produktbild: Complexity Theory Retrospective II

Complexity Theory Retrospective II

49,99 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

27.09.2012

Abbildungen

XI, 339 p. 7 illus.

Herausgeber

Lane A. Hemaspaandra + weitere

Verlag

Springer Us

Seitenzahl

339

Maße (L/B/H)

23,5/15,5/2 cm

Gewicht

540 g

Auflage

Softcover reprint of the original 1st ed. 1997

Sprache

Englisch

ISBN

978-1-4612-7319-6

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

27.09.2012

Abbildungen

XI, 339 p. 7 illus.

Herausgeber

Verlag

Springer Us

Seitenzahl

339

Maße (L/B/H)

23,5/15,5/2 cm

Gewicht

540 g

Auflage

Softcover reprint of the original 1st ed. 1997

Sprache

Englisch

ISBN

978-1-4612-7319-6

Herstelleradresse

Springer-Verlag KG
Sachsenplatz 4-6
1201 Wien
AT

Email: GPSR Kontakt

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)
  • Produktbild: Complexity Theory Retrospective II
  • 1 Time, Hardware, and Uniformity.- 1 Introduction.- 2 Background: Descriptive Complexity.- 3 First Uniformity Theorem.- 4 Variables That Are Longer Than log nBits.- 5 Uniformity: The Third Dimension.- 6 Variables That Are Shorter Than log nBits.- 7 Conclusions.- 2 Quantum Computation.- 1 The Need for Quantum Mechanics.- 2 Basic Principles of Quantum Mechanics.- 3 Computing with Quantum Registers.- 4 Separating Two Classes of Functions.- 5 Shor’s Factoring Algorithm.- 6 Building a Quantum Computer.- 3 Sparse Sets versus Complexity Classes.- 1 Introduction.- 2 Earlier Results for Turing Reductions.- 3 Earlier Results for Many-One Reductions.- 4 Bounded Truth Table Reduction of NP.- 5 The Hartmanis Conjecture for P.- 6 Conclusions.- 4 Counting Complexity.- 1 Introduction.- 2 Preliminaries.- 3 Counting Functions.- 4 Counting Classes.- 5 Relativization.- 6 Other Work.- 5 A Taxonomy of Proof Systems.- 1 Introduction.- 2 A Technical Exposition.- 3 The Story.- 6 Structural Properties of Complete Problems for Exponential Time.- 1 Introduction.- 2 Strong Reductions to Complete Sets.- 3 Immunity for Complete Problems.- 4 Differences between Complete Sets.- 5 Other Properties and Open Problems.- 7 The Complexity of Obtaining Solutions for Problems in NP and NL.- 1 Introduction.- 2 Computing Optimal Solutions: The Class FPNP.- 3 Bounded Queries to NP.- 4 Computing Solutions Uniquely: The Class NPSV.- 5 Nonadaptive Queries to NP: The Class FPNPtt.- 6 A Look inside Nondeterministic Logspace.- 7 Conclusions.- 8 Biological Computing.- 1 Introduction.- 2 The One-Molecule Processor.- 3 A Brief Introduction to Biochemistry.- 4 Computational Molecules.- 5 The Microarchitecture of CNA Computers.- 6 A Brief Discussion of Adleman’s Model Versus Our Model.- 7 Conclusions.- 9 Computing withSublogarithmic Space.- 1 Are Sublogarithmic Space Classes of Any Interest?.- 2 The Alternating Sublogarithmic Space World.- 3 Adding Randomness.- 4 Special Limitations of Machines with a Sublogarithmic Space Bound.- 5 A Survey of Lower Space Bound Proofs.- 6 Conclusions and Open Problems.- 10 The Quantitative Structure of Exponential Time.- 1 Introduction.- 2 Preliminaries.- 3 Resource-Bounded Measure.- 4 Incompressibility and Bi-Immunity.- 5 Complexity Cores.- 6 Small Span Theorems.- 7 Weakly Hard Problems.- 8 Upper Bounds for Hard Problems.- 9 Nonuniform Complexity, Natural Proofs, and Pseudorandom Generators.- 10 Weak Stochasticity.- 11 Density of Hard Languages.- 12 Strong Hypotheses.- 13 Conclusions and Open Directions.- 11 Polynomials and Combinatorial Definitions of Languages.- 1 Introduction.- 2 Polynomials.- 3 Representation Schemes and Language Classes.- 4 Strong versus Weak Representation.- 5 Known Upper and Lower Bounds on Degree.- 6 Polynomials for Closure Properties.- 7 Probabilistic Polynomials.- 8 Other Combinatorial Structures.- 12 Average-Case Computational Complexity Theory.- 1 Introduction.- 2 Average Polynomial Time.- 3 Average-Case Completeness.- 4 Randomization.- 5 Hierarchies of Average-Case Complexity.- 6 A Brief Survey of Other Results.