Re:The TSP Isn't NP Complete
by ColinWright on Monday December 30, 2013 @12:36PM
(#6985645)
The maximum is bounded by the number of edges times the maximum edge cost.
[ Parent
| on HN ]
It depends what encoding is used. If the edge costs are integers, this is true. Also such bounds are possible for rational costs (but you have to pay more attention). It gets a lot more difficult if non-rational edge weights are allowed.
I think we're talking here about problems that can be fed to a digital computer and hence can be represented by a finite number of bits. I believe that would exclude non-rational weights.
No, it wouldn't exclude non-rational weights. Consider for example the field Q[sqrt{2}]. Any element a+b * sqrt{2} of it can be represented by two rational numbers a, b. Since any field extension is a vector space (in this case of dimension 2) the addition can be implemented trivially and the multiplication is
(a1, a2) * (b1, b2) = (a1 * b1 + 2 * a2 * b2, a1 * b2 + a2 * b1) (#)
A formula for inversion can easily be derived from (#).
TLDR: there are different kinds of encoding than binary fractions.
Re:The TSP Isn't NP Complete
by ColinWright on Monday December 30, 2013 @04:59PM
(#6987296)
Not necessarily - quantities like, for example, sqrt(2) can be represented symbolically. So can quantities like e and pi. You can get around this by multiplying all edge costs by twice the number of edges divided by the smallest non-zero difference between costs, then rounding to integers. Or something similar.