0
$\begingroup$

I can run, for instance, np.linalg.eig or np.linalg.svd on my computer in polynomial time. However, my understanding is that if the intermediate steps require too many bits to express and give NaNs or Infs, I get a "SVD did not converge error."

Can one use the SVD in a polynomial time reduction to prove the NP-hardness of something?

Looking at Sipser's book, I see that all "reasonable" models of computation are polynomial time equivalent. How careful does one need to be in describing something like this. Do I need to define a finite field in which all entries in all matrices with which I query the SVD oracle will reside?

Do I need to find in the literature a proof that if the entries of the matrix are bounded by a certain number of bits every step of the SVD computation will be bounded by a certain number of bits?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ See a matrix analysis book such as the one by Golub and van Loan to see the details of the poly-time computability of SVD. Indeed one should pay attention to the bit complexity of the intermediate steps. $\endgroup$
    – Chandra Chekuri
    Jun 22 at 21:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.