资源描述：
《5Some basic complexity results.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TelAvivUniversity,Fall2004Lecture5Lecturer:OdedRegevLatticesinComputerScienceSomebasiccomplexityresultsScribe:IshayHavivInthislecturewepresentsomebasiccomputationalcomplexityresultsrelatedtolatticeproblems.Wefocusmainlyontheclosestlatticevectorproblem(CVP)anditsvariants.1DecisionversusS
2、earchRecallthatintheclosestvectorproblemwearegivenalatticeandatargetvector(whichisusuallynotinthelattice)andwearesupposedtofindthelatticepointthatisclosesttothetargetpoint.Moreprecisely,onecanconsiderthreevariantsoftheCVP,dependingonwhetherwehavetoactuallyfindtheclosestvector,finditsdistan
3、ce,oronlydecideifitiscloserthansomegivennumber:²DecisionalCVP:GivenalatticebasisB2Zm£n,atargetvectort2Zm,andarationalr2Q,determinewhetherdist(t;L(B))·rornot.²OptimizationCVP:GivenalatticebasisB2Zm£nandatargetvectort2Zm,finddist(t;L(B)).²SearchCVP:GivenalatticebasisB2Zm£nandatargetvectort
4、2Zm,findx2ZnthatminimizeskBx¡tk.Itisnotdifficulttoseethatasolutiontothesearchvariantimmediatelyimpliesasolutiontotheop-timizationvariant;furthermore,asolutiontotheoptimizationvariantimpliesasolutiontothedecisionalvariant.Thenextlemmashowsthattheconversealsoholds,andhenceallthreevariantsar
5、einfactpolyno-miallyequivalent.LEMMA1SearchCVPcanbesolvedinpolynomialtimegivenanoraclethatsolvesdecisionalCVP.PROOF:GivenabasisB=(b1;:::;bn)andatargett,ourfirstgoalistodeterminer=dist(t;L(B))(inotherwords,wefirstsolvetheoptimizationvariantofCVP).Theideaistousebinarysearch.MorePnprecisely,
6、defineR=i=1kbikandnoticethat0·r·R,soRisa(rough)upperboundonthedistance.Moreover,noticethatr,asthel2distancebetweentwointegerpoints,mustbethesquarerootofaninteger.Hence,thereareonlyR2possiblevaluesforr.Therefore,abinarysearchfordist(t;L(B))usingthedecisionalCVPoracleneedsatmost2logRsteps,
7、whichispolynomialintheinputsize.Nowthatwefoundr=dist(t;L(B)),ourgoalistofindtheclosestvectortot.Ourfirstobservationisthatitisenoughtofindtheclosestlatticevectortoanypointoftheformt+vwherev2L(B)(sincewecantheneasilysubtractvfromtheanswertoobtaintheclosestvectortot).Inordertodothis,
