On Saxe’s theorems about the complexity of the Distance Geometry Problem
2026
Read On Saxe’s theorems about the complexity of the Distance Geometry Problem (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-00001.txt.
Introduction
Maël Kupperschmitt and Leo Liberti revisit a 1979 summary by James Saxe on the hardness of the Distance Geometry Problem. Saxe left many proofs as sketches, with gaps even where full proofs were claimed. The authors supply a commentary that fills in detail and restates the results in clearer form. Their aim is understanding rather than new theorems, and the paper suits readers who want Saxe made readable. It is a careful piece of expository repair.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62437 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602.00001
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Saxe’s theorems about the complexity of the Distance Geometry Problem Abstract 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 [ 16 ] . Many of the proofs in his paper are sketches, and even the whole proofs do not have all the details. In this paper we provide a commentary to Saxe’s results and hopefully more understandable versions thereof. Maël Kupperschmitt 1 , Leo Liberti 2 1 École Polytechnique, Institut Polytechnique de Paris, F-91129 Palaiseau, France Email: [email protected] 2 LIX CNRS, École Polytechnique, Institut Polytechnique de Paris, F-91128 Palaiseau, France Email: [email protected] August 10, 2026 1 Introduction This paper aims at clarifying the results about the computational complexity of the Euclidean Distance Geometry Problem (EDGP) given in [ 16 ] , which is an “extended summary” published in a 1979 conference proceedings volume. The full archival paper was never published after the conference. The first part of the technical report [ 17 ] , however, looks like it might have been a candidate to the missing full paper. Unfortunately, though, many proofs in [ 17 ] are as sketchy as those of the extended summary [ 16 ] , which also contains some graphical errors in [ 16 , Fig. 4.1] (corrected in [ 17 ] ). Given K>0 , the EDGP is the inverse problem to finding a subset of Euclidean distances (with adjacencies) given a set of points in a Euclidean space \mathbb{R}^{K} . It can also be described as drawing a weighted graph in \mathbb{R}^{K} so that the vertices are points and the edges are segments having the same length as the edge weights. Formally, given K>0 and a simple undirected edge-weighted graph G=(V,E,d) (where d:E\to\mathbb{R}_{+} is the edge weight function), one must decide whether there exists a realization x:V\to\mathbb{R}^{K} such that: \forall\{u,v\}\in E\quad\|x_{u}-x_{v}\|_{2}^{2}=d_{uv}^{2}. (1) Note that both sides are squared turn Eq. ( 1 ) into a quadratic (polynomial) equation. The EDGP is natively a decision problem; realizations can be used as certificates for YES instances in an appropriate computational model (see Sect. 1.1.1 ). A realization x can be represented by an n\times K matrix, where n=|V| and the v -th row of x is a K -vector representing the point position of the vertex v in \mathbb{R}^{K} . If K=1 , then a realization is simply an n -vector the v -th component of which is a scalar that indicates the position of v on the real line. If K is fixed, the resulting problem is denoted EDGP K . The generalization of the EDGP to other norms than \ell_{2} is known as the Distance Geometry Problem (DGP), but most of the well-known applications use the \ell_{2} norm [ 13 , 11 , 8 ] . This paper falls in the literary category of commentaries, which are extremely common in religious studies and fairly common in the rest of the human sciences. In mathematics, this genre is typical of the writings about its history. Our aim, however, is not quite historical 1 1 1 For a commentary about the history of mathematics related to the DGP, see [ 10 ] . . Our motivation to re-examine the complexity of the EDGP according to [ 16 ] is that it supports a certain line of research we are undertaking: we want to employ complexity reductions from various problems to the EDGP in order to use its solution algorithms to solve various NP -hard problems [ 9 ] . The rest of this paper is organized as follows. We introduce preliminary notions in Sect. 1.1 . The content of Saxe’s papers is summarized, and some critical points are discussed, in Sect. 2 . In Sect. 3 we provide an in-depth discussion of the membership of EDGP 1 in NP . The main part of this paper is Sect. 4 , where we discuss the reduction from 3sat to the EDGP 1 . The extension of this reduction to the EDGP K is criticized in Sect. 5 , while the extension to edge weights in \mathbb{R} rather than \mathbb{N} is criticized in Sect. 6 . In Sect. 7 we summarize the extension to the “ambiguous” EDGP variant consisting of determining whether an EDGP instance has a single or many incongruent realizations. Sect. 8 concludes the paper. 1.1 Preliminary notions We denote the range of a function f by \mathsf{ran}\,{f} . A function \gamma:\mathbb{R}^{K}\to\mathbb{R}^{K} is a congruence if, given any S\subset\mathbb{R}^{K} , for all x,y\in S we have \|x-y\|_{2}=\|\gamma(x)-\gamma(y)\|_{2} . Rotations, translations, and reflections are all congruences. A pair (\psi,G) where \psi:\mathbb{R}^{K}\to\mathbb{R}^{K} and G=(V,E) with |V|=n is a simple undirected graph is an isometry if, given any finite sequence S=(x_{1},\ldots,x_{n}\;|\;\forall i\leq n\;x_{i}\in\mathbb{R}^{K}) such that |S|=|V| , for all \{u,v\}\in E we have \|x_{u}-x_{v}\|_{2}=\|\psi(x_{u})-\psi(x_{v})\|_{2} . With a small abuse of terminology we say that an isometry defined on a complete graph is a congruence. 1.1.1 Models of computation For a definition of a Turing Machine (TM) see [ 5 ] . A nondeterministic TM is a TM that is capable of following each branch of a test concurrently at no additional computational cost; or, equivalently, an ideal parallel computer with an unbounded number of processors. A model of computation equivalent to the TM but more similar to current computers is the Random Access Machine (RAM) [ 14 ] , which is based on registers holding values. The real RAM [ 18 ] is an abstract model of RAM where each register can hold a real number. See [ 2 ] for notions of computability and complexity concerning the real RAM. 1.1.2 Computational complexity An algorithm is thought of as a function A mapping an input \iota to an output. In this paper we only look at decision problems, so the output is a single bit (YES or NO). The collection of all \iota that A can accept as a valid input is a problem ; we say that a problem consists of instances 2 2 2 Usually we assume that a problem has infinitely many instances, otherwise problems become algorithmically trivial from a theoretical point of view: one can pre-compute solutions for the constant number of instances, then provide them to users in constant time. . The computational complexity of a terminating algorithm is the number of elementary steps, in function of the amount of memory necessary to store \iota , that it performs before termination. Since problems can be solved by more than a single algorithm, we define the complexity of a problem as the complexity of the best algorithm that can solve it. Problems with a polynomial complexity are known as tractable 3 3 3 Polynomial complexity is invariant to many natural interpretations of a given computational model: e.g. constant number of tapes/heads in a TM, constant number of registers in a RAM [ 3 ] . . The class of tractable decision problems is known as P . An interesting class of decision problems which we think have computational complexity larger than any polynomial is that of Nondeterministic Polynomial-time ( NP ): its problems can be solved in polynomial-time only by a nondeterministic TM, which can be thought