4 ms·

Sphere packings and Hamiltonian paths

23 points by krg 14y ago

pjungwir 14y ago
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.
- dubya 14y ago
  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).
- gmaslov 14y ago
  See also: http://en.wikipedia.org/wiki/Experimental_mathematics http://en.wikipedia.org/wiki/Experimental_mathematics
graycat 14y ago
"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.

23 points by krg 14y ago

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.

dubya 14y ago
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).
gmaslov 14y ago
See also: http://en.wikipedia.org/wiki/Experimental_mathematics http://en.wikipedia.org/wiki/Experimental_mathematics

graycat 14y ago

"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.