Re:After almost 20 years, math problem falls
by saulrh on Tuesday July 19, 2011 @03:04AM
(#2779872)
Well, a lot of them can approximate "the" answer to within an arbitrarily and provably small amount, so it's definitions. For example, there is a polynomial-time approximation for euclidean TSP that produces a solution with length at most (1 + epsilon) * optimal.
[ Parent
| on HN ]
That still doesn't answer: Is this formula convex or not. It's a yes or no question, not a probabilistic one.
A probabilistic answer may be useful! But that's not the point of this proof.