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

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

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

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

Publié par

pefav

Nombre de lectures

Langue

English

Computinginthefractalcloud:modulargenericsolversforSATandQ-SATvariantsDenysDuchier,JérômeDurand-Lose?,andMaximeSenotB.P.67L5I9F,OF,-4U5n0i6v7ersOitRéLdÉ’OArNléSanCse,dex2.Abstract.Abstractgeometricalcomputationcansolvehardcombina-torialproblemseﬃciently:weshowedpreviouslyhowQ-SATcanbesolvedinboundedspaceandtimeusinginstance-speciﬁcsignalmachinesandfractalparallelization.Inthisarticle,weproposeanapproachforconstructingaparticulargenericmachineforthesametask.Thisma-chinedeploiestheMap/Reduceparadigmoverafractalstructure.More-overourapproachismodular:themachineisconstructedbycombiningmodules.Inthismanner,wecaneasilycreategenericmachinesforsolv-ingsatiﬁabilityvariants,suchasSAT,#SAT,MAX-SAT.Keywords.Abstractgeometricalcomputation;Signalmachine;Frac-tal;SAT;Massiveparallelism;Modelofcomputation.1IntroductionSincetheirﬁrstformulationsintheseventies,problemsofBooleansatisﬁabilityhavebeenstudiedextensivelyintheﬁeldofcomputationalcomplexity.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-speciﬁci.e.dependedontheformulawhosesatiﬁabilitywastobedetermined.Theprimarycontributionofthepresentpaperistoexhibitaparticulargenericsignalmachineforthesametask:ittakestheinstanceformulaasaninputencoded(inpolynomial-timebyaTuringmachine)inaninitialconﬁguration.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—ﬁnitedensityofinfor-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-

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

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

YouScribe

Le catalogue

Le service

Les conditions