4
$\begingroup$

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?

$\endgroup$
  • 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$ – Suresh Venkat Mar 30 '12 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 Mar 30 '12 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$ – Sasho Nikolov May 17 '15 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 May 17 '15 at 7:31
  • $\begingroup$ @Kaveh Fair enough. Greg is digging out old questions :) $\endgroup$ – Sasho Nikolov May 17 '15 at 8:28
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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