Hacker News Reader

Comment by qclibre22 | Hacker News Reader

Any hope of solving it using quantum computing?

No. Theory offers you a quadratic speed-up of the exponential worst-case running time. And this is the theory. In practice, it looks worse. ....and: exponential worst-case running time is almost never observed in any kind of practical NP-hard optimization problem when using state-of-the-art algorithms on digital computers... and talking about the Steiner tree problem: It is basically solved for all practical matters. Same for the famous travelling salesman problem. Look at this solver: https://www.math.uwaterloo.ca/tsp/concorde.html

Or look at these amazing results: https://www.math.uwaterloo.ca/tsp/star/index.html

Looks like there's a quantum speedup: https://arxiv.org/abs/1904.03581 IIRC there's no epsilon approximation.

NP-complete isn't necessarily bad, depending on the size of inputs, right?

Most problems in this space have reasonable-time approximations that get you close to the right answer for far less computational complexity. Even without ever having looked at Steiner trees before, I guess that there were reasonable approximations, and confirmed that was true without looking too hard. Letting Patterson know about the problem mapping ("your problem is an instance of <X>") is typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments.

(many people say the protein folding problem is NP-complete, but the community generally believes you can predict the folding pathways of all proteins without explicitly running such calculations).

> typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments

And it's hard to overstate his caliber. For those of you who are unfamiliar with the name, Nick mentored Clifford Cocks at GCHQ and pushed him in the direction of inventing public key cryptography.

Reply on news.ycombinator.com