C. Bazgan, B. Escoffier, and V. Paschos, Completeness in standard and differential approximation classes: Poly-(d) apx-and (d) ptas-completeness, Theoretical Computer Science, vol.339, issue.2-3, pp.272-292, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00004059

N. Butko, A. Katharina, V. Lehmann, and . Ramenzoni, Ricochet robots-a case study for human complex problem solving, Proceedings of the Annual Santa Fe Institute Summer School on Complex Systems (CSSS'05), 2005.

J. Chen, B. Chor, M. Fellows, X. Huang, D. W. Juedes et al., Tight lower bounds for certain parameterized NP-hard problems, Inf. Comput, vol.201, issue.2, pp.216-231, 2005.

J. Chen, X. Huang, A. Iyad, G. Kanj, and . Xia, Strong computational lower bounds via parameterized complexity, J. Comput. Syst. Sci, vol.72, issue.8, pp.1346-1367, 2006.

P. Crescenzi, A short guide to approximation preserving reductions, Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, pp.262-273, 1997.

M. Erik-d-demaine, M. Hoffmann, and . Holzer, Pushpush-k is pspace-complete, Proceedings of the 3rd International Conference on FUN with Algorithms, pp.159-170, 2004.

B. Engels and T. Kamphans, Randolphs robot game is np-hard! Electronic Notes in Discrete Mathematics, vol.25, pp.49-53, 2006.

M. Gebser, H. Jost, R. Kaminski, P. Obermeier, O. Sabuncu et al., Ricochet robots: A transverse asp benchmark, International Conference on Logic Programming and Nonmonotonic Reasoning, pp.348-360, 2013.

M. Gebser, R. Kaminski, P. Obermeier, and T. Schaub, Ricochet robots reloaded: A case-study in multi-shot asp solving, Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation, pp.17-32, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01187007

J. Håstad, Clique is hard to approximate within n 1??, Acta Mathematica, vol.182, pp.105-142, 1999.

A. Hesterberg and J. Kopinsky, The parameterized complexity of ricochet robots, Journal of Information Processing, vol.25, pp.716-723, 2017.

M. Holzer and S. Schwoon, Assembling molecules in atomix is hard, Theoretical computer science, vol.313, issue.3, pp.447-462, 2004.

F. Hüffner, S. Edelkamp, H. Fernau, and R. Niedermeier, Finding optimal solutions to atomix, Annual Conference on Artificial Intelligence, pp.229-243, 2001.

C. Icking, T. Kamphans, R. Klein, and E. Langetepe, Exploring an unknown cellular environment, EuroCG, pp.140-143, 2000.

C. Icking, T. Kamphans, R. Klein, and E. Langetepe, Exploring simple grid polygons, International Computing and Combinatorics Conference, pp.524-533, 2005.

R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, J. Comput. Syst. Sci, vol.63, issue.4, pp.512-530, 2001.

T. Ito, E. D. Demaine, J. A. Nicholas, C. H. Harvey, M. Papadimitriou et al., On the complexity of reconfiguration problems, Theoretical Computer Science, vol.412, pp.1054-1065, 2011.

M. Kami?ski, P. Medvedev, and M. Milani?, Complexity of independent set reconfigurability problems, Theoretical computer science, vol.439, pp.9-15, 2012.

D. Lokshtanov, D. Marx, and S. Saurabh, Lower bounds based on the exponential time hypothesis, Bulletin of the EATCS, vol.105, pp.41-72, 2011.

J. Walter and . Savitch, Relationships between nondeterministic and deterministic tape complexities, Journal of computer and system sciences, vol.4, issue.2, pp.177-192, 1970.

. Gerhardj and . Woeginger, Exact algorithms for np-hard problems: A survey, Combinatorial Optimization -Eureka, You Shrink!, vol.2570, pp.185-207, 2003.

D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory of Computing, vol.3, issue.1, pp.103-128, 2007.