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

Description

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

Sujets

• Google
• Metric space
• Signals

Informations

• Publié par: pefav
• Nombre de lectures: 14
• Langue: English

Extrait

Computinginthefractalcloud: modulargenericsolversfor SATandQ-SATvariants DenysDuchier,JérômeDurand-Lose ? ,andMaximeSenot B.P.67 L 5 I 9 F , O F , -4 U 5 n 0 i 6 v 7 ers O it R é L d É ’O A r N lé S an C s e , dex2. Abstract.Abstractgeometricalcomputationcansolvehardcombina- torialproblemsefficiently:weshowedpreviouslyhowQ-SATcanbe solvedinboundedspaceandtimeusinginstance-specificsignalmachines andfractalparallelization.Inthisarticle,weproposeanapproachfor constructingaparticulargenericmachineforthesametask.Thisma- chinedeploiestheMap/Reduceparadigmoverafractalstructure.More- overourapproachismodular:themachineisconstructedbycombining modules.Inthismanner,wecaneasilycreategenericmachinesforsolv- ingsatifiabilityvariants,suchasSAT,#SAT,MAX-SAT. Keywords.Abstractgeometricalcomputation;Signalmachine;Frac- tal;SAT;Massiveparallelism;Modelofcomputation. 1Introduction Sincetheirfirstformulationsintheseventies,problemsofBooleansatisfiability havebeenstudiedextensivelyinthefieldofcomputationalcomplexity.Indeed, themostimportantcomplexityclassescanbecharacterized—intermsofre- ducibilityandcompleteness—bysuchproblemse.g.SATforNP[Cook,1971] andQ-SATforPSPACE[StockmeyerandMeyer,1973].Assuch,itisanat- uralchallengetoconsiderhowtosolvetheseproblemswheninvestigatingnew computingmachinery(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.Butinboth cases,themachineswereinstance-specifici.e.dependedontheformulawhose satifiabilitywastobedetermined.Theprimarycontributionofthepresentpaper istoexhibitaparticulargenericsignalmachineforthesametask:ittakesthe instanceformulaasaninputencoded(inpolynomial-timebyaTuringmachine) inaninitialconfiguration.Wefurtherimproveourpreviousresultsbydescribing ? Correspondingauthor [e-mail]

amodularapproachthatallowsustoeasilyconstructgenericmachinesforother variantsofSAT,suchas#SATorMAX-SAT. Themodelofsignalmachines,calledabstractgeometricalcomputation,in- volvestwotypesoffundamentalobjects:dimensionlessparticlesandcollision rules.Weusehereone-dimensionalmachines:thespaceistheEuclideanreal line,onwhichtheparticlesmovewithaconstantspeed.Collisionrulesdescribe whathappenswhenseveralparticlescollide.Byrepresentingthecontinuoustime onaverticalaxis,weobtaintwo-dimensionalspace-timediagram,inwhichthe motionoftheparticlesarematerializedbysegmentlinescalledsignals. SignalmachinescansimulateTuringmachines,andarethusTuring-universal [Durand-Lose,2005].Theyarealsocapableofanalogcomputationbyusing thecontinuityofspaceandtimetosimulateanalogmodelssuchasBSS’sone [Durand-Lose,2008,Blumetal.,1989]orcomputableanalysis[Durand-Lose, 2009].Othergeometricalmodelsofcomputationexist:coloreduniverses[Ja- copiniandSontacchi,1990],geometricmachines[Huckenbeck,1989],piece-wise constantderivativesystems[Bournez,1997],opticalmachines[Naughtonand Woods,2001]...Allthesemodels,includingsignalmachines,belongtoalarger classofmodelsofcomputation,calledunconventional,whicharemorepowerful thanclassicalones(Turingmachines,RAM,λ-calculus...).Amongallthese abstractmodels,themodelofsignalmachinesdistinguishesitselfbyrealistic assumptionsrespectingthemajorprinciplesofphysics—finitedensityofinfor- mation,respectofcausalityandboundedspeedofinformation—whichare,in general,notrespectedallatthesametimebyothermodels.Nevertheless,signal machinesremainanabstractmodel,withnoaprioriambitiontobephysically realizable,andisstudiedfortheoreticalissuesofcomputersciences. Assignalmachinestaketheiroriginsintheworldofcellularautoma(asillus- tratedinFig.1),theycanalsobeviewedasamassivelyparallelcomputational device.Thisistheapproachproposedhere:weputinplaceafractalcompute grid,thenusetheMap/Reduceparadigmtodistributethecomputations,then aggregatetheresults. Space( Z )Space( R ) Fig.1.Fromcellularautomatatosignalmachines. TheMap/Reducepattern,pioneeredbyLisp,isnowstandardinfunctional programming:afunctionisappliedtomanyinputs(map),thentheresultsare aggregated(reduce).Googleextendedthispatterntoallowitsdistributedcom-