10 Pages
English

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 quantiﬁed boolean formula, instance of Q- SAT the problem of satisﬁability of quantiﬁed 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 deﬁning 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

Computation

Informations

?
?
nn n 2
n2
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
! !
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
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
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
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