Complexity of Algorithms Lctn - Peter Gacs

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

1、winxos11-01-28winxos11-01-28ComplexityofAlgorithmsLectureNotes,Spring1999PeterG´acsBostonUniversityandL´aszl´oLov´aszYaleUniversity1Contents0IntroductionandPreliminaries10.1Thesubjectofcomplexitytheory...........................10.2Somenotationanddefinitions.............................21ModelsofC

2、omputation31.1Introduction.......................................31.2Finiteautomata....................................51.3TheTuringmachine..................................81.4TheRandomAccessMachine.............................181.5BooleanfunctionsandBooleancircuits........................242Alg

3、orithmicdecidability312.1Introduction.......................................312.2Recursiveandrecursivelyenumerablelanguages...................332.3Otherundecidableproblems..............................372.4Computabilityinlogic.................................423Computationwithresourcebounds503.1I

4、ntroduction.......................................503.2Timeandspace.....................................503.3PolynomialtimeI:Algorithmsinarithmetic.....................523.4PolynomialtimeII:Graphalgorithms........................573.5Polynomialspace....................................624Generalth

5、eoremsonspaceandtimecomplexity654.1Spaceversustime....................................715Non-deterministicalgorithms725.1Non-deterministicTuringmachines..........................725.2Witnessesandthecomplexityofnon-deterministicalgorithms...........745.3Generalresultsonnondeterministiccomplexitycl

6、asses...............765.4ExamplesoflanguagesinNP.............................795.5NP-completeness....................................855.6FurtherNP-completeproblems............................896Randomizedalgorithms996.1Introduction.......................................996.2Verifyingapolynomiali

7、dentity............................996.3Primetesting......................................1036.4Randomizedcomplexityclasses............................10827Informationcomplexity:thecomplexity-theoreticnotionofrandomnes