logo资料库

The Nature of Computation.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：19.29M 资料格式：pdf 举报 版权申诉
第1页 / 共1004页
第2页 / 共1004页
第3页 / 共1004页
第4页 / 共1004页
第5页 / 共1004页
第6页 / 共1004页
第7页 / 共1004页
第8页 / 共1004页
资料共1004页，剩余部分请下载后查看
    Cover
    Contents
    Figure Credits
    Preface
    1 Prologue
    1.1 Crossing Bridges
    1.2 Intractable Itineraries
    1.3 Playing Chess With God
    1.4 What Lies Ahead
    Problems
    Notes
    2 The Basics
    2.1 Problems and Solutions
    2.2 Time, Space, and Scaling
    2.3 Intrinsic Complexity
    2.4 The Importance of Being Polynomial
    2.5 Tractability and Mathematical Insight
    Problems
    Notes
    3 Insights and Algorithms
    3.1 Recursion
    3.2 Divide and Conquer
    3.3 Dynamic Programming
    3.4 Getting There From Here
    3.5 When Greed is Good
    3.6 Finding a Better Flow
    3.7 Flows, Cuts, and Duality
    3.8 Transformations and Reductions
    Problems
    Notes
    4 Needles in a Haystack: the Class NP
    4.1 Needles and Haystacks
    4.2 A Tour of NP
    4.3 Search, Existence, and Nondeterminism
    4.4 Knots and Primes
    Problems
    Notes
    5 Who is the Hardest One of All? NP-Completeness
    5.1 When One Problem Captures Them All
    5.2 Circuits and Formulas
    5.3 Designing Reductions
    5.4 Completeness as a Surprise
    5.5 The Boundary Between Easy and Hard
    5.6 Finally, Hamiltonian Path
    Problems
    Notes
    6 The Deep Question: P vs. NP
    6.1 What if P = NP?
    6.2 Upper Bounds are Easy, Lower Bounds Are Hard
    6.3 Diagonalization and the Time Hierarchy
    6.4 Possible Worlds
    6.5 Natural Proofs
    6.6 Problems in the Gap
    6.7 Nonconstructive Proofs
    6.8 The Road Ahead
    Problems
    Notes
    7 The Grand Unified Theory of Computation
    7.1 Babbage's Vision and Hilbert's Dream
    7.2 Universality and Undecidability
    7.3 Building Blocks: Recursive Functions
    7.4 Form is Function: the λ-Calculus
    7.5 Turing's Applied Philosophy
    7.6 Computation Everywhere
    Problems
    Notes
    8 Memory, Paths, and Games
    8.1 Welcome to the State Space
    8.2 Show Me The Way
    8.3 L and NL-Completeness
    8.4 Middle-First Search and Nondeterministic Space
    8.5 You Can't Get There From Here
    8.6 PSPACE, Games, and Quantified SAT
    8.7 Games People Play
    8.8 Symmetric Space
    Problems
    Notes
    9 Optimization and Approximation
    9.1 Three Flavors of Optimization
    9.2 Approximations
    9.3 Inapproximability
    9.4 Jewels and Facets: Linear Programming
    9.5 Through the Looking-Glass: Duality
    9.6 Solving by Balloon: Interior Point Methods
    9.7 Hunting with Eggshells
    9.8 Algorithmic Cubism
    9.9 Trees, Tours, and Polytopes
    9.10 Solving Hard Problems in Practice
    Problems
    Notes
    10 Randomized Algorithms
    10.1 Foiling the Adversary
    10.2 The Smallest Cut
    10.3 The Satisfied Drunkard: WalkSAT
    10.4 Solving in Heaven, Projecting to Earth
    10.5 Games Against the Adversary
    10.6 Fingerprints, Hash Functions, and Uniqueness
    10.7 The Roots of Identity
    10.8 Primality
    10.9 Randomized Complexity Classes
    Problems
    Notes
    11 Interaction and Pseudorandomness
    11.1 The Tale of Arthur and Merlin
    11.2 The Fable of the Chess Master
    11.3 Probabilistically Checkable Proofs
    11.4 Pseudorandom Generators and Derandomization
    Problems
    Notes
    12 Random Walks and Rapid Mixing
    12.1 A Random Walk in Physics
    12.2 The Approach to Equilibrium
    12.3 Equilibrium Indicators
    12.4 Coupling
    12.5 Coloring a Graph, Randomly
    12.6 Burying Ancient History: Coupling from the Past
    12.7 The Spectral Gap
    12.8 Flows of Probability: Conductance
    12.9 Expanders
    12.10 Mixing in Time and Space
    Problems
    Notes
    13 Counting, Sampling, and Statistical Physics
    13.1 Spanning Trees and the Determinant
    13.2 Perfect Matchings and the Permanent
    13.3 The Complexity of Counting
    13.4 From Counting to Sampling, and Back
    13.5 Random Matchings and Approximating the Permanent
    13.6 Planar Graphs and Asymptotics on Lattices
    13.7 Solving the Ising Model
    Problems
    Notes
    14 When Formulas Freeze: Phase Transitions in Computation
    14.1 Experiments and Conjectures
    14.2 Random Graphs, Giant Components, and Cores
    14.3 Equations of Motion: Algorithmic Lower Bounds
    14.4 Magic Moments
    14.5 The Easiest Hard Problem
    14.6 Message Passing
    14.7 Survey Propagation and the Geometry of Solutions
    14.8 Frozen Variables and Hardness
    Problems
    Notes
    15 Quantum Computation
    15.1 Particles, Waves, and Amplitudes
    15.2 States and Operators
    15.3 Spooky Action at a Distance
    15.4 Algorithmic Interference
    15.5 Cryptography and Shor's Algorithm
    15.6 Graph Isomorphism and the Hidden Subgroup Problem
    15.7 Quantum Haystacks: Grover's Algorithm
    15.8 Quantum Walks and Scattering
    Problems
    Notes
    Mathematical Tools
    A.1 The Story of O
    A.2 Approximations and Inequalities
    A.3 Chance and Necessity
    A.4 Dice and Drunkards
    A.5 Concentration Inequalities
    A.6 Asymptotic Integrals
    A.7 Groups, Rings, and Fields
    Problems
    References
    Index
    A
    B
    C
    D
    E
    F
    G
    H
    I
    J
    K
    L
    M
    N
    O
    P
    Q
    R
    S
    T
    U
    V
    W
    X
    Y
    Z
    THENATUREOFCOMPUTATION
    This page intentionally left blank
    TheNatureofComputationCristopherMooreUniversityofNewMexico,AlbuquerqueandSantaFeInstituteStephanMertensOtto-von-GuerickeUniversity,MagdeburgandSantaFeInstitute1
    3GreatClarendonStreet,OxfordOX26DPOxfordUniversityPressisadepartmentoftheUniversityofOxford.ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship,andeducationbypublishingworldwideinOxfordNewYorkAucklandCapeTownDaresSalaamHongKongKarachiKualaLumpurMadridMelbourneMexicoCityNairobiNewDelhiShanghaiTaipeiTorontoWithofficesinArgentinaAustriaBrazilChileCzechRepublicFranceGreeceGuatemalaHungaryItalyJapanPolandPortugalSingaporeSouthKoreaSwitzerlandThailandTurkeyUkraineVietnamOxfordisaregisteredtrademarkofOxfordUniversityPressintheUKandincertainothercountriesPublishedintheUnitedStatesbyOxfordUniversityPressInc.,NewYork©CristopherMooreandStephanMertens2011ThemoralrightsoftheauthorshavebeenassertedDatabaserightOxfordUniversityPress(maker)Firstpublished2011Allrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmitted,inanyformorbyanymeans,withoutthepriorpermissioninwritingofOxfordUniversityPress,orasexpresslypermittedbylaw,orundertermsagreedwiththeappropriatereprographicsrightsorganization.EnquiriesconcerningreproductionoutsidethescopeoftheaboveshouldbesenttotheRightsDepartment,OxfordUniversityPress,attheaddressaboveYoumustnotcirculatethisbookinanyotherbindingorcoverandyoumustimposethesameconditiononanyacquirerBritishLibraryCataloguinginPublicationDataDataavailableLibraryofCongressCataloginginPublicationDataDataavailablePrintedinGreatBritainonacid-freepaperbyCPIAntonyRowe,Chippenham,WiltshireISBN978–0–19–923321–213579108642
    ForTracyandDoro
    This page intentionally left blank
    ContentsFigureCreditsxiiiPrefacexv1Prologue11.1CrossingBridges......................................................11.2IntractableItineraries..................................................51.3PlayingChessWithGod.................................................81.4WhatLiesAhead......................................................10Problems................................................................11Notes..................................................................132TheBasics152.1ProblemsandSolutions.................................................152.2Time,Space,andScaling................................................182.3IntrinsicComplexity...................................................232.4TheImportanceofBeingPolynomial.......................................252.5TractabilityandMathematicalInsight.......................................29Problems................................................................30Notes..................................................................353InsightsandAlgorithms413.1Recursion...........................................................423.2DivideandConquer....................................................433.3DynamicProgramming.................................................533.4GettingThereFromHere................................................593.5WhenGreedisGood...................................................643.6FindingaBetterFlow...................................................683.7Flows,Cuts,andDuality.................................................713.8TransformationsandReductions..........................................74Problems................................................................76Notes..................................................................89vii
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料