Abstract
Given a weighted undirected graph with and a positive integer K, the distance geometry problem (DGP) asks to find an embedding of G such that for each edge we have. Saxe proved in 1979 that the DGP is NP-complete with K = 1 and doubted the applicability of the Turing machine model to the case with K > 1, because the certificates for YES instances might involve real numbers. This chapter is an account of an unfortunately failed attempt to prove that the DGP is in NP for K = 2. We hope that our failure will motivate further work on the question.
| Original language | English |
|---|---|
| Title of host publication | Distance Geometry |
| Subtitle of host publication | Theory, Methods, and Applications |
| Publisher | Springer New York |
| Pages | 85-93 |
| Number of pages | 9 |
| Volume | 9781461451280 |
| ISBN (Electronic) | 9781461451280 |
| ISBN (Print) | 1461451272, 9781461451273 |
| DOIs | |
| Publication status | Published - 1 Nov 2013 |