Best way to determine the minimum dimension of a structure given only distances between points
This problem is sometimes called the low-dimensional Euclidean distance matrix completion or the low-dimensional Euclidean embedding of a weighted graph.

Saxe [Sax79] and Yemini [Yem79] independently showed by a simple reduction from the Partition problem that this problem is NP-complete even in the case of one dimension; that is, the following problem is NP-complete for k=1:

k-dimensional Euclidean distance matrix completion / k-dimentional Euclidean embedding of a weighted graph
Instance: A symmetric matrix M whose entries are either positive integers in binary or “unknown.”
Question: Can the unknown entries in M be filled by real numbers so that M becomes a distance matrix of points in the k-dimensional Euclidean space ℝk?
Equivalently,
Instance: A graph G where each edge has a positive integer weight written in binary.
Question: Can the vertices of G placed in the k-dimensional Euclidean space ℝk so that for each edge of G, the distance between the two endpoints equals to the weight of the edge?

Moreover, Saxe [Sax79] showed (by a more involved reduction from 3SAT) that the k-dimensional Euclidean distance matrix completion remains NP-hard even under the restriction that all known entries in M are either 1 or 2, for every positive integer constant k.  In particular, the problem is NP-complete even when the known entries in M are given in unary.  [Sax79] also contains some hardness results about approximate embedding.

By the way, I do not think that it is trivial that the problem is in NP; note that you need irrational coordinates in some cases when k&gt;1.  I do not know if it is known to be in NP.

References

[Sax79] James B. Saxe.  Embeddability of weighted graphs in k-space is strongly NP-hard.  In Proceedings of the 17th Allerton Conference on Communications, Control, and Computing, pp. 480–489, 1979.  Also in James B. Saxe: Two Papers on Graph Embedding Problems, Department of Computer Science, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini.  Some theoretical aspects of position-location problems. In 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1–8, Oct. 1979.  DOI: 10.1109/SFCS.1979.39