资源描述：
《10 computational complexity.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、10ComputationalComplexity10.1IntroductionNowyouknowthatcertainproblemscanbesolvedbyalgorithmsandcertainotherscannotbe.Indiscussingtheissueofalgorithmicsolvability,youhaveusedtheChurch–Turingthesis,whichasksyoutobelieveinthedictumthatalgorithmsarenothingbuttotalTuringmachines(TTM)thatusepotentia
2、llyinfinitetapes,anidealwhichwewillprobablynotbeabletorealize.Evenifwerealizethisideal,thereisapossibilitythataTMmaytakeanimpracticablylongtimeforgivingananswer.Thiscanhappenevenifthemachineoperatestoofast.Forexample,supposeyouwanttovisit50touristdestinationsspreadoutallovertheearth.Youknowtheco
3、stoftravelingfromeachdestinationtotheother.Dependinguponwhichplacetovisitfirst,andwhichonenext,youhavenow50!possibilitiesfromwhichyouwanttoselecttheonethatisthecheapest.Thenumberofpossibilitiestobeexploredistoolarge,50!>10025.Ifcomputingthecostforoneitineraryvisitingall50destinationstakesabillio
4、nthofasecond(toofastindeed),thenitwillrequirenolessthan1025humanlifetimestodeterminethecheapestitinerary.Thus,algorithmicsolvabilityalonedoesnotsuffice;weareinterestedinpracticalsolvability.Butwhatdoesitmeantosaythataproblemispracticallysolvable?Dowehavetorunanalgorithmforeachinstanceofasolvable
5、problemandthendetermineitspracticalsolvability?Thisisthemostuselessproposal,infact,animpossiblejob.Thesimplereasonisthatthereare,inallprobability,aninfinitenumberofinstancesofaproblem.Again,howdowemeasuretimeinthiscase?Measuringrealtimeisuseless.Astechnologyprogresses,computingtimeforthebasicope
6、rationsreduce,andhowdoweascertainthatourestimateisstillapplicable?Moreover,timeisnottheonlyfactorindiscussingefficiencyorpracticalityofalgorithms.Youmaybeinterestedintheworkingspaceanalgorithmmightdemandtosolveaproblem.Theissueofpracticalitymightalsodependontheparticularcomputationalmodelwechoos
7、e.WefixTuringmachinesasourcomputationalmodel.WewillmeasuretimeintermsofthenumberofstepsaTMtakesingettingasolution.Ofcourse,wemustA.Singh,ElementsofComputationTheory,TextsinComputerScience,327cSpringer-VerlagLondonLimited200932810C
