Yeah, I can believe the problem is NP hard if you need to distinguish ±ε eigenvalues in time O(1) rather than O(logϵ). I don’t understand exact arithmetic very well but it seems wild (e.g my understanding is that no polynomial time algorithm is known for testing 3√n1+3√n2+…+3√nk>0).
Thanks for the clarification! I assumed the question was using the bit computation model (biased by my own experience), in which case the complexity of SDP in the general case still seems to be unknown (https://math.stackexchange.com/questions/2619096/can-every-semidefinite-program-be-solved-in-polynomial-time)
Yeah, I can believe the problem is NP hard if you need to distinguish ±ε eigenvalues in time O(1) rather than O(logϵ). I don’t understand exact arithmetic very well but it seems wild (e.g my understanding is that no polynomial time algorithm is known for testing 3√n1+3√n2+…+3√nk>0).