On Saxe's theorems about the complexity of the Distance Geometry Problem

Maël Kupperschmitt, Leo Liberti

In 1979, James B.~Saxe published an extended summary on the complexity of the Distance Geometry Problem in the proceedings of the 17th Allerton Conference. Many of the proofs in hi…