@inproceedings{ duchier-cie2011,
  code = {(i)},
  author = {Maxime Senot and J{\'e}r{\^o}me Durand-Lose and Denys Duchier},
  title = {{S}olving {Q}-{S}{A}{T} in bounded space and time by geometrical computation},
  booktitle = {8th {I}nternational {C}onference {C}omputability in {E}urope ({C}i{E}'11), {L}ocal {P}roceedings of the 8th {I}nternational {C}onference {C}omputability in {E}urope ({C}i{E}'11)},
  year = {2011},
  month = {06},
  url = {http://hal.archives-ouvertes.fr/hal-00583132/en/},
  address = {Sofia, Bulgarie},
  aeres = {ACTI},
  abstract = {Abstract geometrical computation can solve PSPACE-complete 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 constructions 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 possible boolean valuations by a recursive tree structure relying on a fractal pattern{:} an exponential number of cases are explored simultaneously by a massive parallelism.}}