Solving Q SAT in bounded space and time by geometrical computation

Solving Q-SAT in bounded space and time by geometrical computation Solving Q-SAT in bounded space and time by geometrical computation Denys Duchier 1 , Jérôme Durand-Lose 2 , Maxime Senot 2 1 Team Constraint & Machine Learning 2 Team Graphs & Algorithms Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, Orléans, FRANCE Partially supported by the ANR AGAPE, ANR-09-BLAN-0159-03. CiE '11, Sofia, Bulgaria 28th June 2011 1 / 41

• recursive algorithm


• bounded space


• decision problem


• false ?


• team graphs


• laboratoire d'informatique fondamentale d'orléans


• brute force