@inproceedings{ duchier-sigmac-isaac2010,
code = {(i)},
author = {Denys Duchier and J{\'e}r{\^o}me Durand-Lose and Maxime Senot},
title = {{F}ractal parallelism{:} {S}olving sat in bounded space and time},
booktitle = {{I}{S}{A}{A}{C} '10, {I}nt. {S}ymposium on {A}lgorithms and {C}omputation},
year = {2010},
month = dec,
url = {http://hal.archives-ouvertes.fr/hal-00511230/en/},
team = {LIFO},
aeres = {ACTI},
abstract = {Abstract geometrical computation can solve NP-complete problems efficiently{:} any boolean constraint satisfaction problem, instance of SAT, can be solved in bounded space and time with simple geometrical constructions involving only drawing parallel lines on a Euclidean space-time plane. Complexity as the maximal length of a sequence of consecutive segments is quadratic. The geometrical algorithm achieves massive parallelism{:} an exponential number of cases are explored simultaneously. The construction relies on a fractal pattern and requires the same amount of space and time independently of the SAT formula.}}