10 Pages
English

Solving Q SAT in bounded space and time by geometrical computation

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 efficiently: 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.g. SAT for NP or Q-SAT for PSPACE, and coding them in the new computation model.

  • bounded space

  • exactly matching rule

  • boolean

  • required meta-signals

  • meta-signals speed

  • space-time diagram

  • signals

  • x1


Subjects

Informations

Published by
Reads 13
Language English

SolvingQ-SATinboundedspaceandtimeby
geometricalcomputation

DenysDuchier,JérômeDurand-Lose,MaximeSenot
LIFO,UniversityofOrleans,BP6759,F-45067ORLEANSCedex2,FRANCE.

Abstract.
AbstractgeometricalcomputationcansolvePSPACE-com-
pleteproblemsefficiently:anyquantifiedbooleanformula,instanceofQ-
SAT–theproblemofsatisfiabilityofquantifiedbooleanformula–can
bedecidedinboundedspaceandtimewithsimplegeometricalconstruc-
tionsinvolvingonlydrawingparallellinesonanEuclideanspace-time.
Complexityasthemaximallengthofasequenceofconsecutivesegments
isquadratic.Weusethecontinuityofthereallinetocoverallthepossi-
blebooleanvaluationsbyarecursivetreestructurerelyingonafractal
pattern:anexponentialnumberofcasesareexploredsimultaneouslyby
amassiveparallelism.
Keywords.
Abstractgeometricalcomputation;Signalmachine;Q-SAT;
Fractalcomputation;Massiveparallelism;Unconventionalcomputation.

1Introduction
Whendefiningandstudyinganewmodelofcomputation,especiallyanuncon-
ventionnalone,thesequestionsarisenaturally:whatcanwecompute(interms
ofdecidability),howcanwecomputeit,andwhatdoesitcost(intermsofcom-
plexity)?Answerscouldbefoundbytakingrepresentativeproblemsofclassical
complexityclasses,e.g.SATforNPorQ-SATforPSPACE,andcodingthemin
thenewcomputationmodel.ThiswasdoneforNP-problemswithactivemem-
branessystem[Păun,2001]andwithanhyperbolicspaceofcellularautomata
[MargensternandMorita,2001].Similarly,somesolutionsforQ-SATwerepro-
posedwithP-systemsandmembranes[AlhazovandPérez-Jiménez,2007],and
withclosedtimelikecurvesinrelativisticcomputation.Weshowedin[Duchier
etal.,2010]that
signalmachines
,ageometricalandabstractmodelofcomputa-
tion,arecapableofsolvingSATinboundedspaceandtime.Inthepresentpaper,
weextendthisresulttothehighercomplexityclassPSPACEbydescribinga
geometricalconstructionsolvingQ-SATthrough
fractalparallelization
,stillin
constantspaceandtime.
Wealsoofferamorepertinent,model-specific,notionoftime-complexity,
namely
collisiondepth
,whichisquadraticforourproposedconstruction.
Thegeometricalcontextproposedhereisthefollowing:dimensionless
parti-
cles
moveuniformlyontherealaxis.Whenasetofparticlescollide,theyare
replacedbyanewsetofparticlesaccordingtoachosencollectionof
collision
rules
.Weconsiderthetemporalevolutionofthesesystemsthroughtheir
space-
timediagram
,inwhichtracesoftheparticlesarematerializedbylinessegment

thatwecall
signals
.Thespace-timediagramofasignalmachineconstitueda
geometricalcomputation
.
Modelsofcomputation,conventionalornot,arefrequentlybasedonmath-
ematicalidealizationsofphysicalconceptsandinvestigatetheconsequences,on
computationalpower,ofsuchabstractions(quantum,membrane,closedtime-
likecurves,blackholes...).However,oftentimes,theidealizationissuchthat
itmustbeinterpretedeitherasallowinginformationtohaveinfinitedensity
(e.g.anoracle),ortobetransmittedatinfinitespeed(globalclock,nospatial
extension...).Onthisissue,themodelofsignalmachinesstandsincontradis-
tinctionwithotherabstractmodelsofcomputation:itrespectstheprincipleof
causality,densityandspeedofinformationarefinite,asarethesetsofobjects
manipulated.Nonetheless,itremainsaresolutelyabstractmodelwithnoapri-
oriambitiontobephysicallyrealizable;itdealswiththeoreticalissuessuchas
computationalpower.
ItispossibletodoTuring-computationwithsuchasystem[Durand-Lose,
2005]andeventodoanalogcomputationbyasystematicuseofthecontinuityof
spaceandtime[Durand-Lose,2009a,b].Other
geometrical
modelsofcomputa-
tionexistandallowtocompute:coloreduniverses[JacopiniandSontacchi,1990],
geometricmachines[Huckenbeck,1989],piece-wiseconstantderivativesystems
[Bournez,1997],opticalmachines[NaughtonandWoods,2001]...
Mostoftheworktodateinthisdomain,called
abstractgeometricalcom-
putation
(AGC),hasdealtwiththesimulationofsequentialcomputationseven
thoughthemodel,seenasacontinuousextensionofcellularautomata,isinher-
entlyparallel(seeFig.1).Inthepresentpaper,wedescribeamassivelyparallel
evaluationofallpossiblevaluationsforagivenpropositionalformulaandwe
provideawaytocollecttheresults.Thisisthefirsttimethatparallelismis
reallyusedinAGC.

Space(
Z
)Space(
R
)
Fig.1.
Fromcellularautomatatosignalmachines.
Toachievemassiveparallelism,wefollowafractalpatterntoadepthof
n
(for
n
propositionalvariables)inordertopartitionthespacein
2
n
regions
correspondingtothe
2
n
possiblevaluationsoftheunquantifiedformula.Wecall
theresultinggeometricalconstructionthe
combinatorialcomb
ofpropositional
assignments.Withasignalmachine,suchanexponentialconstructionfitsin
boundedspaceandtimeregardlessofthenumberofvariables.
Oncethecombinatorialcombisinplace,itisusedtoimplementabinary
decisiontreeforevaluatingtheformula,whereallbranchesareexploredinparal-
lel.Finally,alltheresultsarecollectedandaggregatedrespectingthequantifiers

oftheQ-SATformulatoyieldthefinalanswer.Ourconstructionproceedsin
stages:wegenerateandcalibrateabeamofsignalsencodingtheformula,making
surethatitfitsinthecombinatorialcomb,wepropagateitthroughthebinary
decisiontree,wecomputethetruthvaluewhenreachingeachvaluation,and
finalizetheansweratthetopofthediagram.
SignalmachinesarepresentedinSection2.Sections3to7detailstepby
stepourgeometricalsolutiontoQ-SAT:splittingthespace,codingtheformula,
broadcastingtheformula,evaluatingitandfinalizingtheanswerbycollecting
theresults.ComplexitiesarediscussedinSection8andconclusionandremarks
aregatheredinSection9.
2Definitions
Satisfiabilityofquantifiedbooleanformulae.
Q-SATisthesatisfiability
problemforquantifiedbooleanformulae(QBF).AQBFisaclosedformulaof
theform:
φ
=
Qx
1
Qx
2
...Qx
n
ψ
(
x
1
,x
2
,...,x
n
)
where
Q
∈{∃
,
∀}
and
ψ
is
aquantifier-freeformulaofpropositionallogic.SATisthefragmentofQ-SAT
usingonlytheexistentialquantifier.
Q-SATis
PSPACE-complete
[StockmeyerandMeyer,1973]:itcanbesolved
byapolynomial-spacealgorithmandanyPSPACE-problemcanbereducedin
polynomialtimetoQ-SAT.Theclassicalalgorithmisrecursive:givenaformula
Qxφ
(
x
)
,itrecursivelydeterminesthesatisfiabilityof
φ
(
true
)
and
φ
(
false
)
,
thenaggregatestheresultswith

if
Q
=

orwith

if
Q
=

.
Signalmachines.
Signalmachinesareanextensionofcellularautomatafrom
discretetimeandspacetocontinuoustimeandspace.Dimensionlesssignals/par-
ticlesmovealongthereallineandrulesdescribewhathappenswhentheycollide.
Signals.
Each
signal
isaninstanceofa
meta-signal
.Theassociatedmeta-signal
definesits
velocity
andwhathappenwhensignalsmeet.Figure2presentsavery
simplespace-timediagram.Timeisincreasingupwardsandthemeta-signalsare
indicatedaslabelsonthesignals.Meta-signalsarelistedontheleftofFig.2.

Meta-SignalsSpeed
0w→−d
−→
iv
3
1ih→−3olb

a

c

k
-3

Fig.2.
Computingthemiddle

Collisionrules
{
w
,
d

i

v
}

{
w
,
h
−→
i
,
l
−→
o
}
−−←→−{
lo
,
w
}

{
back
,
w
}
{
h
−→
i
,
b

a

c

k
}

{
w
}

Generally,weuseover-linearrowstoindicatethedirectionofpropagationof
ameta-signal.Forexample,
a
←−
and

a

denotetwodifferentmeta-signals;butas
canbeexpected,theyhavesimilarusesandbehaviors.Similarly
b
r
and
b
l
are
different;botharestationary,butoneismeanttobetheversionforrightand
theotherforleft.

Collisionrules.
Whenasetofsignalscollide,theyarereplacedbyanewsetof
signalsaccordingtoamatchingcollisionrule
{
σ
1
,...,σ
n
}→{
σ
1
0
,...,σ
0
p
}
where
all
σ
i
and
σ
j
0
aremeta-signals.Arulematchesasetofcollidingsignalsifits
left-handsideisequaltothesetoftheirmeta-signals.Bydefault,ifthereisno
exactlymatchingruleforacollision,thebehaviorisdefinedtoregenerateexactly
thesamemeta-signals.Insuchacase,thecollisioniscalled
blank
.Collisionrules
canbededucedfromspace-timediagramasonFig.2.Theyarealsolistedon
therightofthisfigure.
Signalmachine.
Asignalmachineisdefinedbyasetofmeta-signals,asetof
collisionrules,andaninitialconfiguration,i.e.asetofparticlesplacedonthe
realline.Theevolutionofasignalmachinecanberepresentedgeometricallyasa
space-timediagram
:spaceisalwaysrepresentedhorizontally,andtimevertically,
growingupwards.TheexampleofFig.2computesthemiddle:thenew
w
is
locatedexactlyhalfwaybetweentheinitialtwo
w
.
3Combinatorialcomb
Inordertodeterminebybruteforcewhetheraunquantifiedpropositionalfor-
mulawith
n
variablesissatisfiable,
2
n
casesmustbeconsidered.Thesecases
canberecursivelyenumeratedusingabinarydecisiontree.
Theintuitionisthatthedecisionforvariable
x
i
willberepresentedbya
stationarysignal:thespaceontheleftshouldbeinterpretedas
x
i
=
false
,
andthespaceontherightas
x
i
=
true
.Thenwewillsimilarlysubdividethe
spacestotheleftandtotheright,withstationarysignalsfor
x
i
+1
,andsoon
recursivelyforallvariablesasillustratedinFig.3(a).

x
3
x
2
x
3
x
1
x
3
x
2
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
3
x
2
x
2
x
2
x
2
wx
2
x
2
w
xx11x1

(a)Casesidentification(b)Divisionprocess
Fig.3.
Combinatorialcombfor
3
variables.
→−−Startingwithtwoboundingsignals
w
andaninitiator
start
,spaceisrecur-
sivelydividedasshowninFig.3(b).ThefirststepworksexactlyasinFig.2,but

thencontinuesontoadepthof
n
:thecountingisrealizedbyusingsuccessively
m
−→
0
,
m
−→
1
,
m
−→
2
...Thenecessaryrulesandmeta-signalsaresummarizedinTab.1.

Meta-SignalSpeedCollisionrules
s

t

ar

t
,
s

t

ar

t
l

o
,

a

3{
s

t

ar

t
,
w
}

{
w
,
s

t

ar

t
l

o
,
m
−→
0
}
m
−→
0
,
m
−→
1
,
m
−→
2
...1{
s

t

ar

t

,
w
}

{
a
←−
,
w
}
olx
1
,
x
2
,
x
3
...0{
w
,
a
←−
}

{
w
,

a

}
m
←−
0
,
m
←−
1
,
m
←−
2
...-1{

a

,
w
}

{
a
←−
,
w
}
a
←−
-3{
m
−→
i
,
a
←−
}

{
a
←−
,
m

i

+

1
,
x
i
,
m

i

+

1
,

a

}
b
l
,
b
r
0{

a

,
m
←−
i
}

{
a
←−
,
m

i

+

1
,
x
i
,
m

i

+

1
,

a

}
{
m
−→
n
,
a
←−
}

{
b
r
}
{

a

,
m

n

}

{
b
l
}
Table1.
Meta-Signalsandcollisionrulestobuildthecomb.

Sinceeachlevelofthetreeishalftheheightofthepreviousone,thefulltree
canbeconstructedinboundedtimeregardlessofitssize.Also,notethatthe
bottomlevelofthetreeisnot
x
n
but
b
r
and
b
l
.Theseareusedbothtoevaluate
theformulaandtoaggregatetheresultsasexplainedlater.

4Formulaencoding
Inthissection,wewillexplainhowtorepresenttheformulaasasetofsignals.
Thisisillustratedwitharunningexample:
φ
=

x
1

x
2

x
3
x
1

(
¬
x
2

x
3
)
.
Weconsiderthequantifier-freesubformulaof
φ
:
x
1

(
¬
x
2

x
3
)
whichcanbe
viewedasatreewhosenodesarelabeledbysymbols(connectivesandvariables).
Theevaluationoftheformulaforagivenassignmentisabottom-upprocess
thatpercolatesfromtheleavestowardtheroot.Inordertomodelthatprocess,
weshallrepresenteachnodeofthetreebyasignal.InFig.4(a),eachnodeis
additionallydecoratedwitha
path
fromtherootuniquelyidentifyingitsposition
inthetree:thusweareabletoconvenientlydistinguishmultipleoccurrences
ofthesamesymbol.Thesedecoratedsymbolsprovideconvenientnamesfor
therequiredmeta-signals(seeFig.4(b)).Thusaformulaofsize
t
requiresthe
definitionof
2
t
meta-signals.
Thesignalsforallsubformulaearesentalongparalleltrajectoriesandform
a
beam
.Theyarestackedinthediagraminorderofnesting,inner-mostsubfor-
mulaefirst.Thisorderisimportantfortheprocessofpercolationthatwilltake
placeattheend.Thewidthofthebeammustbecalibratedtohaveaproper
propagationthroughthetree:itmustbesufficientlynarrowtofitinthetoplevel
(see[Duchieretal.,2011,App.A]foradetailledexplanationandproofs).

5Propagatingthebeam
Theformula’sbeamisnowpropagateddownthedecisiontree.Foreachdecision
point,thebeamisduplicated:onepartgoesthrough,theotherisreflected.

∧rl∨x1¬
rl
x
3
rr
clrx2(a)Labeledtree

Meta-SignalSpeed
−←∧←−
,
∨←−
r
,
¬
rl
-1
←−←−←−
x
l
1
,
x
r
2
lc
,
x
r
3
r
-1
→−−∧→
,
−∨→
r
,
¬
rl
1
→−→−x
l
1
,
x
r
2
lc
,
x

r

3
r
1
(b)Generated(c)Initialdisplaying
signals
Fig.4.
Compilingtheformula

(d)Corridors

Thus,byconstruction,everybranchofthebeamtreeencountersadecision
pointforeveryvariableatleastonce.Ifwemakethebeamsufficientlynarrow,
theguaranteebecome“exactlyonce,”asshowninFig.4(d).
Whenthebeamencountersadecisionpoint(astationarysignalforavari-
able
x
i
),thenasplitoccursproducingtwobranches.Exceptforthesignoftheir
velocity,mostsignalsremainidenticalinbothbranches;most,exceptthosecor-
respondingtooccurrencesof
x
i
:thosebecome
false
intheleftbranchand
true
intherightbranch.Fig.5(a)showsthebeamintersectingthedecisionsig-
−←→−nalforvariable
x
1
.Notehowtheincidentsignal
x
l
1
becomes
f
l
ontheleftand
→−t
l
ontheright;thepathdecorationispreservedsince,asweshallsee,itis
essentiallaterforthepercolationprocess.Thisisachievedbythecollisionrule:
−→←−−→
{
x
l
1
,
x
1
}→{
f
l
,
x
1
,
t
l
}
.Sinceadecisionpointisencounteredexactlyoncefor
eachvariableoneachbranchofthelane,atthebottomofthetree,allsignals
correspondingtooccurrencesofvariableshavebeenassignedabooleanvalue.

6Evaluatingtheformula
Rememberhow,attheverybottomofthedecisiontree,weaddedanextra
divisionusingsignals
b
l
or
b
r
:theirpurposeistoinitiatethepercolationprocess.
b
l
isforstartingthepercolationprocessofaleftbranch,while
b
r
isforaright
branch.Figure5(c)zoomsononecaseofourexample.
Theinvariantisthatallsignalsthatreach
b
r
havedeterminedbooleanval-
−←→−ues.When
t
l
reaches
b
r
,itgetsreflectedas
T
l
.Thechangefromlowercaseto
uppercaseindicatesthatthesubformula’ssignalisnowabletointeractwiththe

−→←−−→
{

r
,
T
rl
}

{
t
()
r
}
−→←−−→
{
t
()
r
,
T
rr
}

{
t
r
}
−→←−−→
{
id
r
,
T
rr
}

{
t
r
}
−←{
∨−→
r
,
F
rl
}

{
i

d

r
}
−→←−−→
{
t
()
r
,
F
rr
}

{
t
r
}
−→←−−→
{
id
r
,
F
rr
}

{
f
r
}
(a)Split(b)Collisionrulestoevaluatethe(c)Evaluationatthe
disjunction

r
bottomofthecomb
Fig.5.
Split,evaluationprocessandrulesforaconnective.

signalofitsparentconnective.Thestackingorderensuresthatreflectedsignals
ofsubformulaewillinteractwiththeincomingsignaloftheirparentconnective
beforethelatterreaches
b
r
.Thisenforcestheinvariant.
Aconnectiveisevaluatedbycollidingwiththe(uppercased)booleansignals
ofitsarguments.Forexample,thedisjunctioncollideswithitsfirstargument.
Dependingonitsvalue,itbecomestheone-argumentfunctionidentityorthe
constant
true
.ThisisthewaytherulesofFig.5(b)shouldbeunderstood.
Notehowthepathdecorationsareessentialtoensurethattherightsub-
formulaeinteractwiththerightoccurrenceso

f

c

onnectives.Conjunctionsand
negationscanbehandledsimilarly.Finally,
store
projectsthetruthvalueof
theformula’srooton
b
r
whereitistemporarillystoreduntil
co

l

le

c

t
startsthe
aggregationoftheresults.

7Collectingtheresults
Attheendofthepropagationphase,theresultsofevaluatingtheunquanti-
fiedformulaforallpossibleassignmentshavebeenstoredasstationarysignals
replacingthe
b
l
and
b
r
signals.Wemustnowevaluatethequantifiedformula.
Rememberthateachlevelofthecombcorrespondstoavariable:level
1
stands
for
x
1
,...Foraggregatingalltheresults,wewill"undo"theconstructionprocess
ofthebinarytreebymixingtwobytwotheresultsofevaluationswithrespect
totheinitialquantifiers.
Ateachsplitofthebeam–
i.e.
whenitmeetsthestationarysignalscoding

−−→←−−

x
i
atthe
i
th
levelofthetree–thesignal
collect
(resp.
collect
)(attheverytop
ofthebeam)changesthestationaryx
i
intoastationaryL
i
Q
(resp.R
i
Q
),where
ii

Q
i
denotesthequantifierfor
x
i
in
φ
,andL(resp.R)indicatesthedirectionin
whichtoemitthecombinedresultoftrying
x
i
=
false
(comingfromtheleft)
and
x
i
=
true
(comingfromtheright).Thebooleanconnectivetoeffectthe
combinationdependsonthetypeofthequantifier:

for

and

for

.This
collectionprocessisillustratedinFig.6.

Fig.6.
Collectingtheresults.

Thespace-timediagramfortheentireconstructionisshowninFig.7.

8Complexities
Wenowturntoacrucialquestion:whatisthecomplexityofourconstruction
asafunctionofthesizeoftheformula?Whatisameaningfulwaytomeasure
thiscomplexity?
Thewidthoftheconstructionmeasuresthespacerequirement:itisindepen-
dentoftheformulaandcanbefixedtoanyvaluewelike.Theheightmeasures
thetimerequirement:itisalsoindependentoftheformulabecauseofthefractal
constructionandthecontinuityofspace-time.Ifmorevariablesareinvolved,the
combgainsextralevels,butitsheightremainsboundedbyafractal,theinfinite
binarytree.
Asaconsequence,whilewidth(space)andheight(time)arethenatural
continuousextensionsoftraditionalcomplexitymeasuresusedinthediscrete
universeofcellularautomata,inthecontextofabstractgeometricalcomputa-
tions,theylooseallpertinence.
Insteadweshouldregardourconstructionasacomputationaldevicetrans-
forminginputsintooutputs.Theinputsaregivenbytheinitialstateofthe
signalmachineatthebottomofthediagram.Theoutputisthecomputedresult
thatcomesoutatthetop.Thetransformationisperformedinparallelbymany
threads:athreadhereisanascendingpaththroughthediagramfromaninput

totheoutput.Theoperationsthatare“performed”bythethreadareallthe
collisionsfoundalongthepath.
Thus,ifweviewthediagramasan
acyclicgraphofcollisions(vertices)and
signals(arcs),timecomplexitycanthen
bedefinedasthemaximalsizeofachain
ofcollisionsandspacecomplexityasthe
maximalsizeofananti-chain
i.e.
asetof
signalspairwiseun-related.
Let
t
bethesizeoftheformulaand
n
thenumberofvariables.Atthebottom
levelofthecomb,thereisananti-chain
oflengthapproximately
t
2
n
,makingthe
spacecomplexityexponential.Generation
ofthecomb,initiation,propagation,eval-
uationandaggregationcontributealong
anypathanumberofcollisionsatmost
linearinthesizeoftheformula.However,
intersectionsofincidentandreflectedbran-
chesateveryleveladd
O
(
nt
)
becausethere
are
O
(
n
)
levelsandthebeamconsistsof
O
(
t
)
parallelsignals.Thusthetimecom-
plexityis
O
(
nt
)
.
Fig.7.
Thewholediagram.
Itshouldalsobepointedoutthatthe
compilationintoarationalsignalmachine
isdoneinpolynomialtimeandonlyfivedistinctspeedsareinvolved.Algorithms
togeneratethemachinefromtheformulaandallthecollisionrulescanbefound
in[Duchieretal.,2011,App.B].
9Conclusion
Inthisarticle,wehaveshownhowtoachievemassiveparallelismwithsignal
machines,bymeansofafractalpattern.Wecallthis
fractalparallelism
anditis
anovelcontributioninthefieldofabstractgeometricalcomputation.Wehave
describedhowthisapproachisabletosolveQ-SATinboundedspaceandtime.
Thecomplexityisnothiddeninsidethecompilationofthemachine(done
inquadratictime)norintheinitialconfiguration(whichisverysimple)andall
thespeedsareconstant.Since,clearly,timeandspacearenolongerappropri-
atemeasuresofcomplexity,wehavealsoproposedtoreplacethemrespectively
bythemaximumsizeofachainandananti-chaininthespace-timediagram
regardedasadirectedacyclicgraph.Accordingtothesenewdefinitions,our
constructionhasexponentialspacecomplexityandquadratictimecomplexity.
Itseemsnaturaltodrawaconnexionbetweentheconstructionwepropose
andBooleancircuits,andweplantoinvestigatetherelation.However,signal
machinesaddressanadditionalconcern,whichBooleancircuitsdonot;namely,
thatcomputationstakeplacenotonlyovertime,butalsooverphysicalspace,

andthat,inthisrespect,theyarepotentiallylimitedbyanyboundplacedon
thespeedatwhichinformationmaytravel.
Anyformulacanbecompiledintoasignalmachine.Thenextstepisto
provideasinglesignalmachinethatisgenericforQ-SAT—
i.e.
itcansolveany
instanceofQ-SAT—sothattheformulawouldonlyhavetobecompiledinto
aninitialconfiguration.Additionally,wewillcontinueourinvestigationswith
complexityclasseshigherinthehierarchy,suchasEXPTIMEorEXPSPACE.
Bibliography
A.AlhazovandM.J.Pérez-Jiménez.UniformsolutionofQ-SATusingpolarization-
lessactivemembranes.InJ.Durand-LoseandM.Margenstern,editors,
Machines,
Computations,andUniversality,5thInternationalConference(MCU’07)
,number
4664inLNCS,pages122–133.Springer,2007.
O.Bournez.Someboundsonthecomputationalpowerofpiecewiseconstantderivative
systems.In
ICALP’97
,number1256inLNCS,pages143–153,1997.
D.Duchier,J.Durand-Lose,andM.Senot.Fractalparallelism:SolvingSATinbounded
spaceandtime.InO.Cheong,K.-Y.Chwa,andK.Park,editors,
21stInternational
SymposiumonAlgorithmsandComputation(ISAAC’10)
,number6506(Part1)in
LNCS,pages279–290.Springer,2010.
D.Duchier,J.Durand-Lose,andM.Senot.SolvingQ-SATinboundedspaceandtime
bygeometricalcomputation(extendedversion).ResearchReportRR-2011-03,LIFO,
Universitéd’Orléans,2011.URLhttp://www.univ-orleans.fr/lifo/rapports.php.
J.Durand-Lose.Abstractgeometricalcomputation:Turingcomputingabilityandun-
decidability.InB.Cooper,B.Löwe,andL.Torenvliet,editors,
NewComputational
Paradigms,1stConf.ComputabilityinEurope(CiE’05)
,number3526inLNCS,
pages106–116.Springer,2005.
J.Durand-Lose.Abstractgeometricalcomputation3:Blackholesforclassicaland
analogcomputing.
Nat.Comput.
,8(3):455–572,2009a.
J.Durand-Lose.Abstractgeometricalcomputationandcomputableanalysis.In
J.CostaandN.Dershowitz,editors,
InternationalConferenceonUnconventional
Computation2009(UC’09)
,number5715inLNCS,pages158–167.Springer,2009b.
U.Huckenbeck.Euclidiangeometryintermsofautomatatheory.
Theoret.Comp.Sci.
,
68(1):71–87,1989.
G.JacopiniandG.Sontacchi.Reversibleparallelcomputation:anevolvingspace-
model.
Theoret.Comp.Sci.
,73(1):1–46,1990.
M.MargensternandK.Morita.NPproblemsaretractableinthespaceofcellular
automatainthehyperbolicplane.
Theoret.Comp.Sci.
,259(1-2):99–128,2001.
T.J.NaughtonandD.Woods.Onthecomputationalpowerofacontinuous-space
opticalmodelofcomputation.InM.Margenstern,editor,
Machines,Computations,
andUniversality(MCU’01)
,number2055inLNCS,pages288–299,2001.
G.Păun.Psystemswithactivemembranes:AttackingNP-Completeproblems.
Journal
ofAutomata,LanguagesandCombinatorics
,6(1):75–90,2001.
L.J.StockmeyerandA.R.Meyer.Wordproblemsrequiringexponentialtime.In
5th
ACMSymposiumonTheoryofComputing(STOC’73)
,volume16,pages1–9,1973.