[emuch.net]ebooksclub.org__acm07_completeness_and_reduction_in_algebraic_complexity_theory

《[emuch.net]ebooksclub.org__acm07_completeness_and_reduction_in_algebraic_complexity_theory》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、CompletenesandReductioninAlgebraicComplexityTheoryPeterBurgiserDedicatedtoBrigitteandLadinaPrefaceOneofthemostimportantandsuccessfultheoriesincomputationalcomplexityisthatofNP-completeness.ThisdiscretetheoryisbasedontheTuringmachinemodelandachievesaclassicationofdiscretecomputationalproblemsacc

2、ordingtotheiralgorithmicdiculty.Turingmachinesformalizealgorithmswhichop-erateonnitestringsofsymbolsoveranitealphabet.Bycontrast,inalgebraicmodelsofcomputation,thebasiccomputationalstepisanarithmeticoperation(orcomparison)ofelementsofaxedeld,forinstanceofrealnumbers.Herebyoneassumesexactari

3、thmetic.In1989,Blum,Shub,andSmale[12]combinedexistingalgebraicmodelsofcomputationwiththeconceptofuniformityanddevelopedatheoryofNP-completenessoverthereals(BSS-model).Theirpapercreatedarenewedinterestintheeldofalgebraiccomplexityandinitiatednewresearchdirections.TheultimategoaloftheBSS-model(an

4、ditsfutureexten-sions)istouniteclassicaldiscretecomplexitytheorywithnumericalanalysisandthustoprovideadeeperfoundationofscienticcomputation(cf.[11,101]).AlreadytenyearsbeforetheBSS-paper,Valiant[107,110]hadproposedananalogueofthetheoryofNP-completenessinanentirelyalgebraicframework,inconnection

5、withhisfamoushardnessresultforthepermanent[108].WhilethepartofhistheorybasedontheTuringapproach(#P-completeness)isnowstandardandwell-knownamongthetheoreticalcomputersciencecommunity,hisalgebraiccompletenessresultforthepermanentsreceivedmuchlessattention.TherstaccountofValiant'salgebraictheorywi

6、thelaboratedproofswasvonzurGathen'ssurvey[41].Amorerecenttreatment,withdierentproofs,canbefoundinthelastchapterofthebook[21]byBurgisseretal.Inthisresearchmonograph,wefurtherdevelopValiant'sapproach,andcla-rifyitsconnectionsbothtothediscreteandtotheBSS-model.Wethinkthisaddsconsiderablytoourunder

7、standingoftheconceptofcompletenessinalgeb-raicmodelsofcomputation.Thisbookistheauthor'sHabilitationsschriftinmathematicsattheUniversityofZurich.Itisorganizedasfollows.TheintroductionoverviewsthethreeknowntheoriesofNP-complet