1
$\begingroup$

I've seen on Wikipedia; that set covering cannot be approximated in polynomial time to within a factor mentioned above. Unless $NP$ has quasipoly-time algorithms.

Now, this must pertain to classical algorithms and does not mention any approximation algorithms that may only work in nature.

(eg. Things like Amoebas solving $TSP$ problems)

  • Do any single-cell organisms show any promise in solving $NP$-hard problems in polynomial-time?

  • Or approximating them better than any known classical algorithms?

$\endgroup$
2
$\begingroup$

In the realm of classical physics (where you don't need quantum mechanics to predict what is going on), we have no known method of computation that will be significantly faster than a standard classical computer. Indeed, it is a standard belief that none exists.

The one exception is quantum mechanics. Quantum computers are believed to be able to solve some problems significantly faster than classical computers -- though only a few special problems; for most, they offer no benefit (and quantum computers are not expected to offer any significant speedup for NP-complete problems). It is a standard belief that no physical process that can be described by quantum mechanics offers any significant speedup over a quantum computer (in particular, a quantum computer is universal and can simulate any quantum mechanical process).

In short, the answer to your question is "no, there is no known physical process that holds any promise for solving NP-hard problems in polynomial time".

$\endgroup$
2
  • $\begingroup$ Why does a $2^n$ algorithm matters if I have a non-classical computer that has a $2$^$1-trillion$ exponential speedup to solve $SAT$ instances with 1-trillion+ variables in seconds? $\endgroup$ – Dingle Berry Jun 30 '20 at 22:38
  • $\begingroup$ If you can solve instances with 1-trillion variables in seconds, solving instances with 1-trillion and 60 variables will still require several ages of the universe. $\endgroup$ – Steven Jun 30 '20 at 22:55

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.