Let's say I have a complete weighted graph with $n$ nodes and strictly positive weights. I'd like to find the smallest $d\in\mathbb{N}$ such that there exists a set of $n$ points in $x\_n\in\mathbb{R}^d$ with Euclidean distance equal to the corresponding edge weights.

A couple questions:

Is there a $d$ bounded by some constant for every $n$, or does it depend explicitly on the size of n?

What is the complexity class of this problem?

So I am faced with solving a system of $\frac{n(n-1)}{2}$ multivariate quadratic equations, right? What's the best way to tackle this? I have read a bit that maybe resultant elimination is applicable, but I am not exactly sure how to apply it. Ideas?

Update:

Okay, so I found another necessary condition based on Joseph's answer. All but one of the eigenvalues of a Euclidean distance matrix are negative.