10 Pages
English

Solving Q SAT in bounded space and time by

Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 34
Language English

?
?
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.tthetheustformbruladaseapropagationsetitofesignals.wThisaisesillustratedwwiththeaot.runningorderexample:moDivisionthat(b)cess,ticationeidenrepresenCaseseac(a)noxofxtreexyxsignal.xFig.xexhxdexadditionallyxwithxpxfromxroxuniquelywntitstheositionlevthe(seethhierwtare2011,toA]vatlyexplanationmprooSinceof:sameariables.bvThesecesssymforolsbvidecomonorialenientnamesathebinmeta-siCom(seethe4(b)).ofuseacfTherforulasubformsizearerequireswhicdenitionFig.hcanmeta-signals.bsignalseallviewulaeedsenasalongatratreeewhoseandnoadeseare.labareeledkbinydiagramsymorderbnesting,olssubfor-(connectivulaeesThisandivimpariables).tThetheecessvpaluationthatoftaktheplaceformtheulaTheforofabgimvbencaliassignmenateistoavbaottom-uperprothroughcesstree:thatmpbercolatessucienfromnarrothetowin.topWele[Ducconsideretheal.,quanApp.tier-freeforsubformdetailledulaandofofs).!
w collect
^
!
! storew
W8 w !W8! ^l r wx _ W1 7
w ! rW7! _w
W7 !w rrrrrl W xx 7! 3: 3 w W6 !w rlW6! :w
W5 !rlc w rlcx W x2 5! 2
w W4 !
w lW x4! 1w
W3 w !W m3! 0
w W2! awW 2! w
W^ _ : 1
a! C6!a
1 2 3
W1!! ! ! a^ _ : C5
!! ! W! a 1
1 2 3
xi
xi
!
x1 1
!
! !
f ; g!f ; ; g1 11
1rrx,thet;elorlcvxhe,thosel(xx1tialrlhes.,ticalr,,in(c)inInitialthedispleftlaas(b)Thiseledying(d)tCorridorssignFig.most4.brancCompilingtothebformbranculabranc5wsPropagatingdecisionthe.bsignaleamfThelformisula'ssee,bpeamedi,sMeta-Signalno(a)wopropagatedfordotheirwnytheremaindecbisionmost,tree.respFccurrencesor:eacfalsehfdecisionandprighoinFig.t,)thebbtheamnalisxduplicated:hooneidenpartxgoecomesesontrlhrough,thethepathotheredisereected.isThforus,pro-1ac.yaollisionpxtxencounfGeneratedexactlyforlhwariablebranceacExceptbranctheofofevatcitb,ofsignalstree,idensignalsinondingothohes;ofexceptariablescor-vondingboassignedofbrlcolethosevecome6inaluatingleformtRememhertruew,thetheteryh.ottom5theatree,shoetheaneamdivisiontersectingsigeasig-bfororariabler,theirNoteosewtoincthetercolationlolasbsho-1wnlintheFig.and4(d).tWhenontherighbtheeamdecorationencounpreservterssince,awdecisionshallpitoinessentlater(athestationaryercolationsignalcess.forisahievvbarit-cablerule:rrrxlsignals,eed),thenSpatreesplitloxccursLabprotducingbySinceconstruction,decisionevoineryisbrancteredhonceofeacthveonbheamhtreethencounlane,ttheeottomrstheaalldecisioncorrespptooinccurrencestvforhaeveeryeenvaarioableanatalue.lEveasttheonce.ulaIfbwhoeatmakvebtheofbdecisioneamwsucienaddedtextralusingynnarrolsw,lthebguaran:teepurpbisecomeinitiateexactlyponcepr,cess. success
T
!
;T!
bcollect r
T
!Lcollect 9 collect !store t
^r brrr _ !x store ! r3 store T

rl: ! ! r^ t !
rlc bid rx !2 ! ! r! t() rrTr _
l _ ! t()f !
rl rr! T trr x ! rm 3 ! ! b1 _ r ! l rl^ T Tt() !! !
rrrl t: !
l rlT t! ! !! ! r_ brcollect rlcx id ! !
2 l rl rlcT : F
! !! rrl ! ! l rlc t T fta! b_ ! id rstore
l! T! !m1^ rl:! !
! !r a_ !t() ! rlc! f brrr ! ! !x rl ! a3 rlc l: l tx2 x ! ! !1 m0
! id ! m3 a
r_
!
!
!
disjunctiontherboaluateincomingevalue,toandlesTheubrorCollision.(b)t}jecrthefof{b}arianrroFrst,idenrrules{are}righrmilarlytthe{stored}parenrrensuresFin,parenrreac{enforces}erthe{its}corlendingFthe,therw{should}wrensuretin{of}errexample.Ttruth,rors{t}ofrconnectivtking{reected}ulaerrwithTof,connectivrthe{e}.rin{A}evrlcollidingTercased),signalsrts.{theSplitwith(a)t.righitstbbrancth.yFiguret5(c)iszoyomFig.seonNoteapathonetialfortheisformrwithbowhilees.h,canbrancsresultsFinallytreendsthealuereulultsonevittheorarilttilcasewithcollectsignaltheitsoftresults.e.CollectingstacborderandthatrsignalsWsubformmwillnoteractevtheluatesignalquantheirformt5.eSplit,eforeevlatteraluationhproscessrandThisrulestheforvat.coconnectivnisnectivaluatede.yThewithi(uppnbvoleanarianoftargumenisFthatexample,alldisjunctionsignalsllidesthatitsreacargumenhDepbonrvhaitvecomeseone-argumendeterminedfunctionbtitooroleanconstanvtrueal-Thisues.theWhenaofthetofl5(b)reacbhesunderstobd.rho,theitdecorationsgetsessenreectedtoasthatourrighTsub-lulae.teractThethecthangeccurrencesfromconnectivloConjunctionswnegationsercasebtohandleduppiercase.indic,atesstothatprothetsubformtheula'svsignalofisformnoa'swotablbewheretoiintemptelyrunac-formstartsforaggregationltheossible7replacingtheleftAatheofofphase,propagationprotheercolationspofthealuatingcessunquanstartingiforedtsulavalbpstationaryassignmenishalestoredeenbas(c)signalsEvthealuationlatbthesignals.beottomustofwtheacomthebtiedFig.ula.1
x1
!
thx ii
i i
i
i i
x ii
x =i
x =i
_ 9 ^ 8

Fail
!
Fail Fail
w w
! !LFail Fail 9 success Fail
! ! !! Fail Fail Fail Fail success success Fail successR L8 8
R L R L8 8 8 8
! ! ! ! a a a a a a a a
! ! a a ! a a !a a a a
Lw 9 w
! ! R8 L8a a a a
! !a aa aLw 9 w
! a a
Qsignals),offunctionywhereofQtostationary(space)denoteslevtheturnquant:tierrequiremenforbthemeasuresmeetsFinsitresult,theandthisLthe(resp.likR)ofindicateslthebinarydconierserectionosein,whicahbtoeacemitWthequestion:comourbinedofresultwidthofen-tryingcanwhenvi.e.talsofalsec(comingffitsromatheconsequence,left)(time)andofeaminbintheomputa-trueaggregating(coming.fromstandstheariablerighondst).rThecblevoerolean8connectivnoeatoieectytheascomthebinationformdepy?endsspaceonisthettulaypeenofwtheThequanthetier:itofendenforandsplittinandspace-time.hvforels,eact.bThithesAscollectioneproheighcesstheisuousillustratedcomplexitinseFig.discrete6.cellularTheconspace-timegeometricaldiagramtheyforalltheoren.tire.constructionforiels:shovwntoinpFigre.co7.omcotheRel(resp.hFig.thatCollectingbding6.Qtheats.LComplexitiesstationaryeawtotoincrucialthewhatxsstationarycomplexittheofWhatconstructionaawofysizeotheasuula?hangesisofmeaningfulcatopteam)meeryrebcomplexittheThemeasuresofvconstructionthethelevrequirementit(resp.indepAdentiers.oftheform(atandquanbpxedcollectaelygnalalueiese.theheighinitialmeasurestime)t:formisbindepoftfractalthecollectulatheecausetreethetheconstructionftheareonvuited,ofcomIgaimoresariablesointoolvecttherespbwithnaluationsextraevevofbutsheightremainsuloundedsyrefractal,theinniteotree.watwhilywidthbandotwaretnaturalmixingtinyextensionsbtraditionaltreeybinaryuthedofthecessunivproofconstructionautomata,thethe"undo"textwillabstractecwtions,results,lotheallRememertinence.t n
nt2
O(nt)
O(n)
O(t)
O(nt)
aregivhines,dandennotb.y[Ductheabstractinitialdstateacyclofthethemacsignalvmacalhineableatnorthemebcottomyofistmacheindiagram.theThe9outputhievisWtheelcomputeddescribresultoundedthatofcomesvouttimeatwthebtop.tThedenititransformationformingistimepoinerformedaininparalleldistinctbAlgorithmsyformmbanal.,yarticle,threads:hoaparallelismthreadofherefrisisantheasceendingthispathQ-SAthroughThetheidiagram(donefromcongurationanallit.nnoputoftoetherespoutput.umTheanopregardederationsccordingthatiareinpsignalerformedusbplexityetheoutthreadinaresiallistheolynomialcollisionsvfoundeedsalongolvthgenerateefrompath.andThrulesus,foundifewApp.eInviewetheshodiagramtoasmassivansignalFig.y7.fractalThecallwholepdiagram.andacyclicnographtributionofldcollisionscomputation.(vvertices)hoandhsignalssolv(arcs),intimeandcomplexityyictheanmacthenquadraticbtheehdenedsimple)asspthearemaximalclearlysizespaceofappropri-arecyhainhaofpropcollisionsreplaceandvspacethecomplexitofyandashainthespace-timemaximalasizegraph.ofthesean,antimeti-ctohaiinputsnparalleli.e.sTheThoutputs.theinputscom-Ityalsoatrans-setof.signalsshouldpairwisebun-related.pLetteddevicethatbcompilationetotherationalsizegnalofhinethedoneformpulatimeandonlycomputationalethespnareumvbed.ertoofthevhineariables.theAulatallthecollisionbcanottomelevinelhierotf2011,theB].comConclusionb,thistherewishaaneanwntiw-cachaineofelengthwithappromacximbatelymeansaaaspattern.constructione,thismakingactalthearspacelelismcomplexitityaexpvonencontial.inGenerationeofofthegeometricalcomWb,hainitiation,epropagation,edevwal-approacuationisandtoaggregationeconTtributebalongspaceantime.ycomplexitpathisahiddennnsumdebcompilationertheofhinecollisionsinattime)mostinlinearinitialin(whictheissizeeryofandthetheformeeula.sHoconstanwSince,ev,er,andinaretersectionslongerofateincidenasutsandcomplexitreected,bran-ecvhesalsoatoseevtoerythemlevectielelyaddyrmaximusizeoaregardhainbanecauseti-cthereinareheshoulddiagrameaswdirectedconstructionicexpAtialtocomplexitnewandonsaourInsteadhaslevonenelsspaceandythequadrbteamcconsistscomplexitof.Itseemsnaturalto(STOC2,et.draInwThea288299connexionLbbet(UCwet.eencontheL.constructionywreComputationalprop3:oseJ.andHBoersibleolineanncircuits,Computations,andNP-CompletewexpeTplanvtoURLinutingvandestigateEurtheSpringer,relatidon.compuHoConferwinevEuclidianer,G.signalolvinmacandhineshaddress:99antheadditionaltation.concern,umwhicwithhandBoR.oleanSympci1973rspaceciuitsRepdersioorts.php.not;Tnamelyun-,er,thatrencomputationsConf.tak'05)eLNCS,placDurand-Lose.efornotNat.onlyAbstractopvDershoerUnctime,umbutSpringer,alensoofoSci.vSonertphdysical73(1):146,spacproblemse,cellularandcthat,259inJ.thisorwemosenp(MCUect,5theyParebranes:pAoten(tiakmeyllyWliInmitedorbolumeySolvinganbytimebmetoundcomputationplacedResearconRR-2011-theO,spd'Orl?ans,eedttp://wwatDurand-Lose.whicgeometricalhcoinformationymayyCotraL?wvTel.editors,Anadigms,yilityformeulancan3526b10e005.compiledgeometricalinktoaacompusignal,macJ.hine.etTheandnextanalysis.stepandiseditors,toeproComputationvide,aersinglepagessignal09b.macchineecthatinistheorygenericet.for68(1):7187,Qand-hi.ScomputAanTspace-Thei.e.Sci.itM.canMorita.solvtractabespaceaninyerbinstanceTheofSci.Q-SA1-2T2001.sotonthatD.theds.formpulaofwuous-spaceouldofonlyM.haeditor,vUniversae,toerbLNCS,e2001.compiledPinetottacanJournalinitialLconguration.,A,dditionallySto,andweyeproblemswilltialconAtoniofn,uepagesourSenot.inQ-SAvinestigationsoundedwithandcomplexitbygeoclassesrhicalgher(extendedinersion).thehhierarcorth03,yIF,Univst?uc2011.hhasw.univ-orleans.fr/lifo/rappEXPTIMEJ.orAbstEXPSPactAcomputation:CE.uringBibliographmpyabilitA.andAlhazodecidabilitv.andB.M.opJ.B.P?rez-Jim?nez.e,UniformL.soovliet,lNewutionParof1stQ-SAComputabTinusingopp(CiEolarization-,lessumactivereinmempagesbranes.6116.In2J.J.Durand-LoseAbstractandcomputationM.BlacMargenstern,holeseditors,classicalMachines,nComputations,analogandting.Universality,Comput.5th8(3):45557International2009a.CDurand-Lose.ogeomnferricalenctationecom(MCUutable'07In)Costa,N.nwitz,umInternationalbenceron4664onventionalin2009LNCS,'09)pagesn122133.bSp5715ringer,LNCS,2007.158167.O.20Bournez.U.Someubkobuk.ndsgeometryontermstheautomatacomputational.poroComp.w,er1989.ofJacopinipiecewiseG.contaccstanRevtparallelderivaaion:tevivgemosystems.el.InorICALPComp.'97,,1990.nMargensternumK.bNPerare125le6theinofLNCS,automatapagesthe143153yp,oli1997.plane.D.orDucComp.hier,,J.(Durand-Lose,)and128,MT..NaughSenot.aFdractalWparallelism:oSolvingOnSAcomputationalToinerbaoundedtinspaceopticalanddeltime.compuInInO.MargCheong,stern,K.-Y.Machines,Chandwlitya,'01)andnK.bP205ark,ineditors,pages21st,InternationalG.Symp?un.osiumsystemsonactivAmemlgorithmsAandkingComputationproblems.(ISAAofCutomata,'10)anguages,Combinatoricsn6um1):7590b2001.erJ.6506c(PerarA.tM1)er.inordLNCS,requiringpagesonen279290.time.S5thpringer,CM2010.osiumD.TheDucyhComputingier,'73)J.vDurand-Lose,16,and19,M..