Computation Complexity Lctn - Laszlo Lovasz

《Computation Complexity Lctn - Laszlo Lovasz》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、winxos11-01-28winxos11-01-28ComputationComplexityLaszloLovasztranslation,additions,modicationsbyPeterGacsMarch15,1994Lecturenotesforaone-semestergraduatecourse.Partofitisalsosuitableforanundergraduatecourse,ataslowerpace.Mathematicalmaturityisthemainprerequisite.Contents1Introduction42Models

2、ofcomputation62.1TheTuringmachine:::::::::::::::::::::::::::::::72.2TheRandomAccessMachine::::::::::::::::::::::::::162.3Booleanfunctionsandlogiccircuits:::::::::::::::::::::::222.4Finite-statemachines:::::::::::::::::::::::::::::::292.5ChurchThesis,andPolynomialChurchThesis:::::::::::::::::332.6A

3、realisticnitecomputer::::::::::::::::::::::::::::333Algorithmicdecidability353.1Recursiveandrecursivelyenumerablelanguages::::::::::::::::353.2Otherundecidableproblems:::::::::::::::::::::::::::403.3Computabilityinlogic::::::::::::::::::::::::::::::464Storageandtime524.1Polynomialtime::::::::::::

4、::::::::::::::::::::::534.2Othertypicalcomplexityclasses:::::::::::::::::::::::::604.3Linearspace::::::::::::::::::::::::::::::::::::624.4Generaltheoremsonspace-andtimecomplexity::::::::::::::::644.5EXPTIME-completeandPSPACE-completegames::::::::::::::704.6Storageversustime::::::::::::::::::::::::

5、::::::::725Non-deterministicalgorithms735.1Non-deterministicTuringmachines:::::::::::::::::::::::735.2Thecomplexityofnon-deterministicalgorithms::::::::::::::::755.3ExamplesoflanguagesinNP::::::::::::::::::::::::::805.4NP-completeness:::::::::::::::::::::::::::::::::885.5FurtherNP-completeproblems

6、:::::::::::::::::::::::::926Randomizedalgorithms1006.1Verifyingapolynomialidentity:::::::::::::::::::::::::1006.2Primetesting:::::::::::::::::::::::::::::::::::1036.3Randomizedcomplexityclasses:::::::::::::::::::::::::1077Informationcomplexity(thecomplexity-theoreticnotionofrandomness)1117.1Inform

7、ationcomplexity::::::::::::::::::::::::::::::1117.2Self-delimitinginformationcomplexity:::::::::::::::::::::1157.3Thenotionofarandomsequence::::::::::::::::::::::::1187.4Kolmogorovcomplexityandentropy::::::::::::