Solving Q SAT in bounded space and time by

Description

Niveau: Supérieur, Doctorat, Bac+8
Solving Q-SAT in bounded space and time by geometrical computation Denys Duchier, Jérôme Durand-Lose, Maxime Senot ? LIFO, University of Orleans, BP 6759, F-45067 ORLEANS Cedex 2, FRANCE. Abstract. Abstract geometrical computation can solve PSPACE-com- plete problems e?ciently: any quantified boolean formula, instance of Q- SAT the problem of satisfiability of quantified boolean formula can be decided in bounded space and time with simple geometrical construc- tions involving only drawing parallel lines on an Euclidean space-time. Complexity as the maximal length of a sequence of consecutive segments is quadratic. We use the continuity of the real line to cover all the possi- ble boolean valuations by a recursive tree structure relying on a fractal pattern: an exponential number of cases are explored simultaneously by a massive parallelism. Keywords. Abstract geometrical computation; Signal machine; Q-SAT; Fractal computation; Massive parallelism; Unconventional computation. 1 Introduction When defining and studying a new model of computation, especially an uncon- ventionnal one, these questions arise naturally: what can we compute (in terms of decidability), how can we compute it, and what does it cost (in terms of com- plexity)? Answers could be found by taking representative problems of classical complexity classes, e.

• meta-signals


• exactly matching rule


• space


• time complexity


• computation


• geometrical computation


• space-time diagram


• x1

Sujets

• Time complexity
• Computation

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 34
• Langue: English

Extrait

?
?
TinbarewwithoundedpspaQ-SAcP-systemsebandosedtimetakingbThisysomegeometricaletcomputationpapDen,ysdepthDucrealhier,ANR-09-BLAN-J?r?meyDurand-Lose,dingMaximeeSenotcellularQ-SAprlikJLIFeO,geometricalUnivoundedersittheyTofandOrleans,ofBPprop6759,arti-F-45067particlesORyLEAeNSproblemsCedexT2,AFRANCE.newAbstract.forAbstract[PgeometricalerbcomputationMorita,can-SAsolvosede[AlhazoPSPandAinCE-com-edpletesignalproblemsdelecienSAtly:Inanextendyclassquangeometricaltiedpbtoalsooleandel-spformnamelyula,isinstancegeometricaloffolloQ-eSAnSolvingTorthepropcouldrobbtativlemclassicalofe.g.satisabilitNPyforofandquanintimoedasbwithobranesolean2001]formhulaspace[MargensterncanSimilarlybforewdecided-intbmemoundedandspm?nez,aclosedcecurvandcomputation.timeowith[Ducsimple2010]geometrical,construc-abstracttionscomputa-inofvinolvingandonlypresendrawwingresultparallelcomplexitlinesAondescribingansolvingEuclideanfrspace-talime.inComplexitpacyWasathet,m,aximalylengtholofwhicaforsconstruction.equencetextofisconsecutivdimensionlessemosegmenontWssetistheyquadratic.wWpartiallyeeduseetheAconerstinbuitfoundyyofrepresentheereaoflcomplexitlineclasses,toSAcoforvorerTallPSPtheCE,pcoossi-themblethebcomputationodel.oleanwvdonealuNP-problemsationsactivbmem-ysystema?un,recursivandeantreeypstructureolicrelyingofonautomataaandfractal2001].pattern:,ansolutionsexpQonenTtialerenoumpbwierhofandcasesbranesarevexploredP?rez-simiultaneousl2007],ywithbtimeyeaesmassivrelativisticeWpshawrallelinism.hierKeywal.,ords.thatAbstractmachinesgeometricalacomputation;andSignalmomacofhine;tion,Q-SAcapableT;solvingFTractalbcomputation;spaceMassivtime.etheparallelism;tUnconer,veenthistionaltocomputation.higher1yInPSPtrCEoyductionaWhenconstructiondeningQ-SAandthroughstuactaldyingaralelizationnewstillmoconstandelsofecomputation,time.espeecialoerlymoreanertinenuncon-movecicennotiontionnaltime-complexitone,,thesecquestionslisionarise,naturally:hwhatquadraticcanourwosedeThecomputecon(inproptermshereofthedecidabiwing:litpy),cleshovwuniformlycanthewaxis.ehecomputeait,ofandcollide,whataredoThisesorkitascostsupp(inttermsbofthcom-ANRplexitjecty)?GAPE,Answ0159-03.Z R
nn n 2
n2
accordingtoa2001].)ic1).hosenaluationscollectiongeometricofulationcwolwlisionanrulesexist.ativWcalledetincoaluationntimesiomdpropecrandtgeheunivtempeoral[evorkolutionputationofthoughtheseautomata,systemsethroughatheirtospGC.acnewe-otimepatterndiagroname,ts.inonstwhicbh2009a,b].tracesdelsoftotheSonparticlekspiece-wiseare1997],materializedWbofythlinesometricsegmendealttalthatseenwcelletlycalltsignalsmassiv.ossibleTheositionalspace-timeadiagramThisofreallya)signalvmacFhinesignalconstituedmassivaageofometricinalbctiedomputationresulting.ofMomacdelseofincomputation,ofcspaceonmeveenaltionalcomputa-orallonot,coloreare[Jacopinifrequenhi,tlyhinesbasednonk,math-tematicalsystemsidealizationsmacoftonphoysical.conceptsheanddateinsvactestigatectheGC),consequences,theonsequencomputationalevpmooawextensioner,lofinher-suc(seehtheabser,tractieonsparallel(quanalltum,aluationsmemenbrane,ulaclproosedatime-theliktheeparallelismcurvines,(blac(k(holes.Space.Fig..cellular).aHohines.whievevparallelier,follooftenactimes,athe(foridealizationvistosucspacehossiblethattheitula.mlustconstructionbceositionalinatsuceorptialreontoundederegardldneitherrasandalloiwing[Durand-Lose,informatioOthnrtoometrichamovofetioninniteanddensitwycompute:(e.g.danersesoracle),andortaccto1990],bmace[Huctransmittedeatbinnitecsp1989],eedconstan(globalderivcloec[Bournez,k,opticalnohinesspatialNaughextension.and.o.ds,)..OnMostthistisswueto,intheimodomain,delabstrofgesignalalmacom-hines(Astandshasinwithconsimtradis-oftinctiontiwithcomputationsotherenabstractthemodel,delsasofconcomputation:uousitofrespuectsartheisprincienpleparallelofFig.causalitInypresen,papdensitwydescribandaspelyeedevofofinformationparevnite,forasgivareproptheformsetsandofeobvidejectswmanipulated.yNonetheless,collectitresults.remainsisarstresolthatuisteusedlyAabstractTimemordelSpacewithsetnoTimeapri-aori)am(bition)t1.orombauteatphtoysicallymacrealizable;Titacdealsewithetheoresm,teiwcalfrissuestalsuctohdepthasacomputationalypositionaloariables)particlesorderregionspartitiondingthetheinofwer.correspIttoreplacedisppossiblevtoofdounquanTformuring-computationWwithcalsucthehgeometricalathesystemombinatorial[Durand-Lose,omb2005]propandassignmenevWithensignaltohine,dohanalogexpcomputationnbnycaructisystematictsusebofspacethetimeconesstintheuitumyeofoftables.
N
+
R
back
= Qx Qx :::Qx (x ;x ;:::;x ) Q2f9;8g 1 2 n 1 2 n
Qx (x) ( ) ( )
_ Q =9 ^ Q =8
w ! ! !
w !! ! w !!
!
! !
w
w
proceedsinlinebinatorialtruestages:indicatedwiseangeneratehappandComputingcalibrateCE-probleaarebaluatingeamuousofansignalsspacenco2.dingwthepformolynomialula,enmakingesurethenthatbinaryitttssignals/par-inwhentheciatedcomFigurebinatorialwcomMeta-signalsb,3wtoe,propagatebackitanthroughetheT.binaryvdecisionparal-tree,ewyewherecomputewiththefortruthSignalvellularaluespacewhenDimereacehingeeacEachmeta-signalvveloaluation,nandanalizemethedanswonetherwatimplementhe}topplace,o}fcomthe}diagram.{SignalalgorithmmacPSPhinescanareinpresentotclassicaleursdginformSectioni2.itSectionsdetermi3thetohes7anddetailula,stepthebifyorsteptreeourSignalgeometricalhinessolutionoftofromQ-SAmeT:consplittingandtheispace,mocothedingrulesthehappformcollide.ula,signalbroadcastingoftheTheformdenesula,andevwhenaluatinglsitpresenanderynalizingdiagram.theincreasinganswaemeta-signalsrlabbeylistedcollectingoftheSpresults.aComplexitieshiare3constructiondiscussedinwSectionis8rulesandinconclusion{andhiremarks}are,gathered{inwSecatolynomial-spaceiandony9.A2mDenitionsbSatisabilityreducedofpqtimeuantieQ-SAdThebalgorithmorecoleiane:formulae.ivQ-SAaTulaisntheexploredsatisabil,itrecursivylyproblemnfsorsatisabilitquanoftiedrancbboallolefalsean,formaggregatesulaeresults(QBF).formAtheQBFeviswithaifcloseddecisionform.ulamachines.ofmactheareform:extensionanswcnalautomatathediscreteyielditoandulatoformtinTtimeQ-SAspace.thensofonlesstiersticlesquanvthealongectingrealrespandddescribewhattensaggregatheydSignals.nhaisctedinstancecolleaare.whereassoresultsmeta-signalheitstcityllwhataenandsig,aismeet.a2quantstier-freevformsimpleulae-timeofTipropisositionaluplogic.ardsSAnTtheisaretheasfragmenelstthFinallysignals.hiarelel.on}leftonlyFig.thMeta-Signalseeedthe0tialdivquanttier.1OurlobackQ-SAT-3is2.PSPFig.er.ACE-c{ompleusedteit[StoCollisionc{kmey,erdivandisMweyber,,1973]:loit{canlobwecomsolvtheed,b}yofQ-SA,TbackOnceusingexistenmiddle
! !
div lo
!
hi !
0 0f ;:::; g!f ;:::;g1 n 1 p
0 i j
nn 2
xi
x =i
x =i
xi+1
!
n
! ! !
0 1 2
! ! ! !! !! 0
! ! ! !
0 1 2 !
!
1 2 3 !
!
0 1 2 !
! ! !!i i+1 i i+1
! ! !!i i+1 i i+1
! !n
! !n
rulelisioncol3(a).0ahing,matc,athetowaccordingrtsignalswoftsetwneweana,yofbandreplacedbarevtheybcollide,}sl.signalaof.setrighaallwheresignalsallshoWhenthenrules.band.lisionSpCollleft.xare,me0trta-{sii{gnals.aA,ruindicatelaethematcwillhesleftasignalssetonofscwollidinginitiatorsignalssivif3(b).itsinleft-handonsidecouniselyequal,tonecessarytheinsetrtofatheirandme1ta-signals.viors.By,default,.ifltherehaiswnomexactly,matcwhinggnals;ruleta-sforaa,collision,,the,b}eha}viordirectioniswsdenedmtobregeneratemexactlybthewsamesubmeta-signals.toIntosucwithhtoaandcase,elytheariablescollisioniniswithcalledbblankand.staCollisionisrulesdividedcaninbrsteexactlydeduced2,fromtinspace-timeadiagram:asisonusingFig.m2.mTheymare.alsollistedareonab.1.thebright;t,ofarethisbgure.rSignal.macarlyhi,ne..Amsignalmmacmhine.is-3denedbbrulesyrtatheysetected,of,meta-signals,}artset}ofacollision{rules,aawn}d,an{initialwconguration,mi.e.aadenotesetmofxparticlesmplacedaonnthemreal{line.ofThe,evtoolution,of{a,siegnal}mac,hinescanebtrueeThenrepresenetedsimilarlygeometricallydivideasspacesathespandacthee-timet,diagrstationaryamfor:tspace,issoalwrecursivaforysvrepresenatedillustratedhorizonFig.talStartinglyt,oandoundingtimewvanerticallym,rtgrospacewingrecur-upelywasawnrFig.ds.TheThestepexampleorksofasFig.Fig.2butcomputescontheuesmiddle:tothedepthnewiswtheistinglorealizedcatedyexactlysuccessivhalfwoneabuty,bstationaryetarewotheen.theTheinitialruteswmeta-signalsosummarizedwT.Meta-Signal3eedComstab,inatorialstacomlobdierenIn3ordermto,determinemb,ymbrute.force.whetherxa,unqSimiluaxn.tied.propehaositibonalandforuses-similarmeula.with-1foravbar,irablesCollisionis{satisable,staother,the}cases{m,uststabloeexpande}{{stalloTwlecanMeta-Signalsascollision,t}buildwcombuta}binary{decision,tree.aThe{inatuitionwismethattthe,decision}fordierenvoariablewt}righ{willabaeandrepresen,tedexample,boryFa,stationaryasignal:{theaspacemeta-sigonatheofleftpropagationshould,bmetheinxterpreted,asmforarroersioner-linev}falsev,oandusethe}space{onrthe{righat,aconsidered.GenerallyThesecasesbcan}babe1.recursivandelyrulesenoumeratedtheusingb.3 2 3 1 3 2 3
b b b b b b b bl r x l r x l r x l rw 2 1 2 wx x x x3 3 3 3
x x x x x x x x3 3 3 3 3 3 3 3 ! !x x2 2m m m m 2 !2 2 !2a a a a
w w! 3 3 3 3 a a
x1 !m m1 1 !x x x x a a2 2 2 2
w
2 2 a
wx x1 1 ! m0
!
start1 lo w
3
n
= 9x8x8x x ^(:x _x )1 2 3 1 2 3
x ^(:x _x )1 2 3
t
2t
hleveamathmelproofthetheinner-mosttreeleisahalfusthetheighbtofofproptheroprevioushone,nothetifyingfullenientreebcanFig.bparalleleedconstructedsinatbtoundedusttimetoregardlesstoofshallitsthesize.4(a),Also,decoratednoteotthatintheablebultipleottomol.levcelrequiredofathe3.treectoriesisTheynotinxrst.proforbutwillbwidthreandhabtheltly.vTheseardaInrdelewusedtbdeothbtoInevacaluateistheaformtheulaideandptotree:aggregateetheconrdistinguisheccurrencessusymldecoratedtsproasvexplainedforlater.gnals4ThFoormofulatencojdingformInamthisstacsection,thewofemwillorderexplainortanhoprowercolationtoerepresenend.tthetheustformbruladaseapropagationset