News for hackers. Stuff that matters.
Re:The TSP Isn't NP Complete by tgflynn on Monday December 30, 2013 @04:55PM (#6987270)
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.
Re:The TSP Isn't NP Complete by wolfgke on Monday December 30, 2013 @05:20PM (#6987422)
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.