Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm?

Are known any (classical) approximation algorithms for an $\sf{NP\text{-}complete}$ problem that uses Factoring as oracle?

  • 5
    $\begingroup$ While it might be possible, a deterrent to doing so would be that the true running time of the resulting approximation algorithm would be unknown (and it might not even be polynomial!) $\endgroup$ Commented Mar 30, 2012 at 16:22
  • 2
    $\begingroup$ I think it is not known if Factoring is $\sf{P\text{-}hard}$, so the likely answer is none at the moment. $\endgroup$
    – Kaveh
    Commented Mar 30, 2012 at 17:15
  • $\begingroup$ @Kaveh why do you say that? P-hardness is wrt logspace reductions. How are logspace reductions related to this question? $\endgroup$ Commented May 17, 2015 at 7:26
  • $\begingroup$ @Sasho, this is from 3 years ago so I don't recall exactly, but I think I meant that we don't know how to do it for P so it is unlikely we know how to do it for NP. :) $\endgroup$
    – Kaveh
    Commented May 17, 2015 at 7:31
  • $\begingroup$ @Kaveh Fair enough. Greg is digging out old questions :) $\endgroup$ Commented May 17, 2015 at 8:28

1 Answer 1


There are ways to see that either the answer is probably no, or that the question means more than one thing and has a negotiable answer. On the one hand, the PCP theorem says that many, but not all, NP-hard problems are still NP-hard to approximate. The standard belief is that Grover's search algorithm, which gives you a quadratic speedup but no more than that, is the best quantum algorithm for the hardest NP-hard problems. This leaves fairly little wiggle room to expect any quantum algorithm to have any special relation to approximation to NP-hard problems in general.

Some NP-hard problems are easier to approximate than the ones amenable to the PCP theorem. However, the difficulty of approximation is then highly variable.

Meanwhile Shor's algorithm does something very specific: It finds the period of a periodic function on the integers or on $\mathbb{Z}^n$. This problem is also in the complexity class SZK, for example. Maybe you could cook up an approximation problem to an NP-hard problem that lands you in SZK or period-finding, but I suspect that there aren't any known, natural examples of that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.