Is the Distance Geometry Problem in NP?

Nathanael Beeker (1) , Stéphane Gaubert (1, 2) , Christian Glusa (1) , Leo Liberti (3)

1 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
2 MAXPLUS - Max-plus algebras and mathematics of decision
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

Domaines: Optimisation et contrôle [math.OC]

Nathanael Beeker, Stéphane Gaubert, Christian Glusa, Leo Liberti. Is the Distance Geometry Problem in NP?. Antonio Mucherino and Carlile Lavor and Leo Liberti and Nelson Maculan. Distance Geometry: Theory, Methods, and Applications, Springer, pp.85-93, 2013, 978-1-4614-5127-3. ⟨10.1007/978-1-4614-5128-0_5⟩. ⟨hal-00782869⟩