I just responded to what the OP stated,
in particular the claim of "unsolvable".
The OP said nothing about 1 billion locations.
If the billion locations are all
in a straight line, then
not a problem!
For the set of real numbers R and a positive
integer n and R^n with the usual inner product,
norm, and topology, if the billion points
are in R^n then there is a super cute
algorithm: Find the minimum spanning tree
(with a good algorithm)
of the billion locations and then, for the
solution, just traverse the tree
never returning to a location except
at the end the first. Then for any
x > 0, no matter how small, as the number
of locations grows, and a billion
is quite high, the algorithm
will find a solution within x% of
optimality with probability greater than
1 - x.
What's hard about NP-hard, e.g.,
for the traveling salesman problem
on m locations,
is that
no one knows how to write software that
will solve, with an exactly optimal solution,
worst case problems
in time proportional to a polynomial in m.
But that's nothing like what the OP
claimed.
I was just responding to the OP.
Yes, 0-1 integer linear programming is
also NP-hard. The last case I attacked
had 600,000 variables and 40,016
constraints, and I wrote some software
using Lagrangian relaxation,
e.g., as in
and got a feasible solution within
0.025% of optimality in 905 seconds
on a 90 MHz PC.
Lesson: NP-hard does not always mean hopeless
or "unsolvable"
in practice.
Besides, for 1 billion locations, that would
be one heck of a long time away from
home for the salesman! Besides, as
in nearly all real world optimization
problems, the goal is to save resources,
e.g., time, money, and saving all but
the last penny is fine. Or, why
spend billions to save the last penny?
Actually this point is important:
Early in Garey and Johnson
is a cartoon where a mathematician
is reporting to an executive,
presumably one at Bell who wants
to know the least cost way to
build a communications network,
that he, the mathematician, cannot
solve the executive's problem
but neither can a long line of
other mathematicians.
Nonsense.
All the executive wanted to do
was design a network and save money,
and that goal was quite likely quite
doable.
Instead, sorry, it was as if the mathematician
was looking for a long term job,
that is, claiming that the executive
should fund the mathematician to
get a solution so far not possible.
In a word, the mathematician was lying
in order to land a cushy job, for life!
For nearly anything,
and not just NP-hard problems,
say, a billion,
too much of it is
hard.
Yes, the question of P versus NP is one
of the most astounding unsolved problems
there is. The darned thing seems to be
of even philosophical significance
comparable with the work in set theory
of Kurt Gödel and Paul Cohen, etc.
And, yes, Clay Math in Boston has
a $1 million prize!
Yes, Scott Aaronson has much more to say!
Ah, somewhere I still have Max Zorn's
(as in Zorn's lemma version of the
axiom of choice) copy of Cohen's paper!
I got it from Zorn when at
a tea I asked him what Cohen had proved!
So, yes, I have some interest
in something of such philosophical
interest!
Still, the claim
in the OP that NP-hard problems
are "unsolvable" is nonsense or needs
a nonsense definition of solvable!
If the billion locations are all in a straight line, then not a problem!
For the set of real numbers R and a positive integer n and R^n with the usual inner product, norm, and topology, if the billion points are in R^n then there is a super cute algorithm: Find the minimum spanning tree (with a good algorithm) of the billion locations and then, for the solution, just traverse the tree never returning to a location except at the end the first. Then for any x > 0, no matter how small, as the number of locations grows, and a billion is quite high, the algorithm will find a solution within x% of optimality with probability greater than 1 - x.
What's hard about NP-hard, e.g., for the traveling salesman problem on m locations, is that no one knows how to write software that will solve, with an exactly optimal solution, worst case problems in time proportional to a polynomial in m. But that's nothing like what the OP claimed.
I was just responding to the OP.
Yes, 0-1 integer linear programming is also NP-hard. The last case I attacked had 600,000 variables and 40,016 constraints, and I wrote some software using Lagrangian relaxation, e.g., as in
https://news.ycombinator.com/item?id=8919311
and got a feasible solution within 0.025% of optimality in 905 seconds on a 90 MHz PC.
Lesson: NP-hard does not always mean hopeless or "unsolvable" in practice.
Besides, for 1 billion locations, that would be one heck of a long time away from home for the salesman! Besides, as in nearly all real world optimization problems, the goal is to save resources, e.g., time, money, and saving all but the last penny is fine. Or, why spend billions to save the last penny?
Actually this point is important: Early in Garey and Johnson is a cartoon where a mathematician is reporting to an executive, presumably one at Bell who wants to know the least cost way to build a communications network, that he, the mathematician, cannot solve the executive's problem but neither can a long line of other mathematicians.
Nonsense. All the executive wanted to do was design a network and save money, and that goal was quite likely quite doable.
Instead, sorry, it was as if the mathematician was looking for a long term job, that is, claiming that the executive should fund the mathematician to get a solution so far not possible. In a word, the mathematician was lying in order to land a cushy job, for life!
For nearly anything, and not just NP-hard problems, say, a billion, too much of it is hard.
Yes, the question of P versus NP is one of the most astounding unsolved problems there is. The darned thing seems to be of even philosophical significance comparable with the work in set theory of Kurt Gödel and Paul Cohen, etc.
And, yes, Clay Math in Boston has a $1 million prize!
Yes, Scott Aaronson has much more to say!
Ah, somewhere I still have Max Zorn's (as in Zorn's lemma version of the axiom of choice) copy of Cohen's paper! I got it from Zorn when at a tea I asked him what Cohen had proved! So, yes, I have some interest in something of such philosophical interest!
Still, the claim in the OP that NP-hard problems are "unsolvable" is nonsense or needs a nonsense definition of solvable!