//img.uscri.be/pth/5528ee8a4511486e708a4fe68b4d22dbcdc90d55
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Computing in the fractal cloud: modular generic solvers for SAT and Q SAT variants

21 pages
Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants Denys Duchier, Jérôme Durand-Lose?, and Maxime Senot LIFO, Université d'Orléans, B.P. 6759, F-45067 ORLÉANS Cedex 2. Abstract. Abstract geometrical computation can solve hard combina- torial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This ma- chine deploies the Map/Reduce paradigm over a fractal structure. More- over our approach is modular : the machine is constructed by combining modules. In this manner, we can easily create generic machines for solv- ing satifiability variants, such as SAT, _SAT, MAX-SAT. Keywords. Abstract geometrical computation; Signal machine; Frac- tal; SAT; Massive parallelism; Model of computation. 1 Introduction Since their first formulations in the seventies, problems of Boolean satisfiability have been studied extensively in the field of computational complexity. Indeed, the most important complexity classes can be characterized — in terms of re- ducibility and completeness — by such problems e.g. SAT for NP [Cook, 1971] and Q-SAT for PSPACE [Stockmeyer and Meyer, 1973].

  • fractal grid

  • full fractal

  • bounded space

  • exactly matching rule

  • when solving

  • happens when

  • signals

  • meta-rule

  • combinatorial problems


Voir plus Voir moins
Computinginthefractalcloud:modulargenericsolversforSATandQ-SATvariantsDenysDuchier,JérômeDurand-Lose?,andMaximeSenotB.P.67L5I9F,OF,-4U5n0i6v7ersOitRéLdÉOArNléSanCse,dex2.Abstract.Abstractgeometricalcomputationcansolvehardcombina-torialproblemsefficiently:weshowedpreviouslyhowQ-SATcanbesolvedinboundedspaceandtimeusinginstance-specificsignalmachinesandfractalparallelization.Inthisarticle,weproposeanapproachforconstructingaparticulargenericmachineforthesametask.Thisma-chinedeploiestheMap/Reduceparadigmoverafractalstructure.More-overourapproachismodular:themachineisconstructedbycombiningmodules.Inthismanner,wecaneasilycreategenericmachinesforsolv-ingsatifiabilityvariants,suchasSAT,#SAT,MAX-SAT.Keywords.Abstractgeometricalcomputation;Signalmachine;Frac-tal;SAT;Massiveparallelism;Modelofcomputation.1IntroductionSincetheirfirstformulationsintheseventies,problemsofBooleansatisfiabilityhavebeenstudiedextensivelyinthefieldofcomputationalcomplexity.Indeed,themostimportantcomplexityclassescanbecharacterized—intermsofre-ducibilityandcompleteness—bysuchproblemse.g.SATforNP[Cook,1971]andQ-SATforPSPACE[StockmeyerandMeyer,1973].Assuch,itisanat-uralchallengetoconsiderhowtosolvetheseproblemswheninvestigatingnewcomputingmachinery(quantum,NDA,membrane,hyperbolicspaces...)[Păun,2001,MargensternandMorita,2001,AlhazovandPérez-Jiménez,2007].Thisisthelineofinvestigationthatwehavebeenfollowingwithsignalma-chines[Durand-Lose,2005],anabstractandgeometricalmodelofcomputation.WeshowedpreviouslyhowsuchmachineswereabletosolveSAT[Duchieretal.,2010a]andQ-SAT[Duchieretal.,2010b]inboundedspaceandtime.Butinbothcases,themachineswereinstance-specifici.e.dependedontheformulawhosesatifiabilitywastobedetermined.Theprimarycontributionofthepresentpaperistoexhibitaparticulargenericsignalmachineforthesametask:ittakestheinstanceformulaasaninputencoded(inpolynomial-timebyaTuringmachine)inaninitialconfiguration.Wefurtherimproveourpreviousresultsbydescribing?CorrespondingauthorJerome.Durand-Lose@univ-orleans.fr
amodularapproachthatallowsustoeasilyconstructgenericmachinesforothervariantsofSAT,suchas#SATorMAX-SAT.Themodelofsignalmachines,calledabstractgeometricalcomputation,in-volvestwotypesoffundamentalobjects:dimensionlessparticlesandcollisionrules.Weusehereone-dimensionalmachines:thespaceistheEuclideanrealline,onwhichtheparticlesmovewithaconstantspeed.Collisionrulesdescribewhathappenswhenseveralparticlescollide.Byrepresentingthecontinuoustimeonaverticalaxis,weobtaintwo-dimensionalspace-timediagram,inwhichthemotionoftheparticlesarematerializedbysegmentlinescalledsignals.SignalmachinescansimulateTuringmachines,andarethusTuring-universal[Durand-Lose,2005].TheyarealsocapableofanalogcomputationbyusingthecontinuityofspaceandtimetosimulateanalogmodelssuchasBSS’sone[Durand-Lose,2008,Blumetal.,1989]orcomputableanalysis[Durand-Lose,2009].Othergeometricalmodelsofcomputationexist:coloreduniverses[Ja-copiniandSontacchi,1990],geometricmachines[Huckenbeck,1989],piece-wiseconstantderivativesystems[Bournez,1997],opticalmachines[NaughtonandWoods,2001]...Allthesemodels,includingsignalmachines,belongtoalargerclassofmodelsofcomputation,calledunconventional,whicharemorepowerfulthanclassicalones(Turingmachines,RAM,λ-calculus...).Amongalltheseabstractmodels,themodelofsignalmachinesdistinguishesitselfbyrealisticassumptionsrespectingthemajorprinciplesofphysics—finitedensityofinfor-mation,respectofcausalityandboundedspeedofinformation—whichare,ingeneral,notrespectedallatthesametimebyothermodels.Nevertheless,signalmachinesremainanabstractmodel,withnoaprioriambitiontobephysicallyrealizable,andisstudiedfortheoreticalissuesofcomputersciences.Assignalmachinestaketheiroriginsintheworldofcellularautoma(asillus-tratedinFig.1),theycanalsobeviewedasamassivelyparallelcomputationaldevice.Thisistheapproachproposedhere:weputinplaceafractalcomputegrid,thenusetheMap/Reduceparadigmtodistributethecomputations,thenaggregatetheresults.Space(Z)Space(R)Fig.1.Fromcellularautomatatosignalmachines.TheMap/Reducepattern,pioneeredbyLisp,isnowstandardinfunctionalprogramming:afunctionisappliedtomanyinputs(map),thentheresultsareaggregated(reduce).Googleextendedthispatterntoallowitsdistributedcom-