News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.