This quote is fascinating to me:<p><pre><code> 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.
</code></pre>
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.
"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?"<p>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.<p>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.<p>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.<p>Moral: That a practical problem is in NP-complete (in the sense of the OP) is no reason to give up on the problem.