Sphere packings and Hamiltonian paths | Hacker News Reader

Sphere packings and Hamiltonian paths

bit-player.org

23 pointskrg4 comments

This quote is fascinating to me:

    How much should we worry about this potential omission?
    It depends on your point of view. If you look upon the
    result as a mathematical proof classifying all
    minimally rigid sphere clusters, then the proof has a
    big gap. But, as I noted in my American Scientist
    column, mathematical rigor was not the highest priority
    in this work and was already jeopardized by the use of
    a numerical algorithm (Newton’s method) that is not
    guaranteed to converge in all cases. The original
    motivation for both the Harvard and Yale projects came
    from chemistry and physics, not from geometry and graph
    theory.

So chemistry and physics are using mathematical results, but not strictly proven mathematical results. Does anyone know how common this is? I wonder if we'll see more of it as we accumulate more unproved-but-so-far-so-good mathematical conjectures.

I think physicists are way ahead of mathematics in many areas. The area I know a little about is SLE (Stochastic Loewner Evolution), which is a tool to prove results about a family of conformally invariant processes. Most of the results were known to physicists much earlier, because they just assumed conformal invariance of some limits (supported by simulation) and used that to make calculations.

I've seen the distinction made between mathematics (proven things) and mathematical sciences (experimentally verified beyond any reasonable double).

"There can’t be any efficient way of answering this question (unless P = NP), but is it beyond our ability to close the gap between n = 11 and n = 14?"

No. There might be an "efficient" way even if P is not equal NP. Why? Integer linear programming is in NP-complete, still there are at least countably infinitely many integer linear programs that can solve just by inspection. There may be a simple solution the OP's question.

More generally, that a problem X is and example of a class of problems in NP-complete doesn't mean that problem X is difficult to solve. In particular, integer linear programming problems are common in production and scheduling in business; for some of them, can get solutions; for some of them, the solutions are valuable for the business.

E.g., once I had a 0-1 integer linear programming problem with 40,000 constraints and 600,000 variables. In 905 seconds on a 90 MHz PC (yes, Virginia, at one time that was considered a fast computer!) I found a feasible solution and showed that its objective function value had to be within 0.025% of optimality. Then once when discussing design of IP networks in Plano, TX, some people concluded that I must be fibbing because integer linear programming is in NP-complete. No fibbing. Not all integer linear programming problems are difficult. Besides, likely I didn't find an optimal solution, just a solution close to optimality. But for a related point, in business being close to optimality might save nearly all the money and be plenty good.

Moral: That a practical problem is in NP-complete (in the sense of the OP) is no reason to give up on the problem.

Reply on news.ycombinator.com