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).
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).