Fundamentally, because big-O notation operates on the size of the input, not the number of elements in the input.
As a trivial example, let's say you represent each city by their latitude/longitude encoded as integers, with 0 being ...well 0, and 180,000,000 being 180W. Let's also say you can encode each city's longitude with 0 meaning 0-90W, or 1, meaning 90-180W and its latitude 0 being 0-45N and 1 being 45-90N. The second encoding is a much, much, MUCH easier problem for a large number of cities. By using a small, fixed number of bits, you've effectively capped the size of your input as 4 bits. You just have 4 locations a city might be in; you can solve this approximation with a simple 16 element lookup table. By discarding bits in the city's coordinates, you're approximating the solution, not finding the exact solution.
This is not just a triviality. The dynamic programming algorithm to solve subset sum runs in O(MN) time, where M is the number of integers, and N is the sum you're looking to achieve. Running subset sum on 1,000,000 numbers that you want to add up to 100 is going to run in milliseconds, but running that algorithm on 1,000,000 numbers that add up to 1,000,000,000 is going to take a while. (10,000,000 times as long) Subset sum is NP-complete, but it's only NP-complete because you're not talking about the value of the sum, you're talking about the number of bits it takes to represent the sum. One of the other problems in Karp's NP-completeness paper reduces to subset sum by summing up 1s or 0s shifted by i bits for each element in the input; so if there are 7 elements, the N for subset sum will be on the order of 2^7. If there are 1,000 elements, N for subset sum will be on the order of 2^1,000.
You can approximate subset sum by dividing every number by some constant. So if you want to know which integers of 3,4,5,6,7,8 sum to 12, you can divide everything by 3 and figure out which integers of 1,2,2,2,3,3 sum up to 4. (round up) If you were to take that 1,000 element problem, compute the sum to be some ludicrous integers on the order of 2^1,000, then divide everything by 2^980, and then solve the approximation in O(M * 2^20) time, what have you done? Well you've simply discarded 98% of the inputs. You haven't gained anything by reducing to subset sum and approximated the solution; you could have simply discarded all by 20 of the inputs and solved that with the brute force algorithm, whatever it is.
That's what this paper is doing by handwaving away the low order bits. They're saying you can solve TSP in O(m^k * n^j) time, where m is the number of cities, k and j and some arbitrary fixed constants, and n is the number of bits in the mantissa of your floating point scheme, ie, only if n is a small fixed constant. They've found an approximation of an NP-complete problem, which is something we already have in droves.
Comments
Fundamentally, because big-O notation operates on the size of the input, not the number of elements in the input.
As a trivial example, let's say you represent each city by their latitude/longitude encoded as integers, with 0 being ...well 0, and 180,000,000 being 180W. Let's also say you can encode each city's longitude with 0 meaning 0-90W, or 1, meaning 90-180W and its latitude 0 being 0-45N and 1 being 45-90N. The second encoding is a much, much, MUCH easier problem for a large number of cities. By using a small, fixed number of bits, you've effectively capped the size of your input as 4 bits. You just have 4 locations a city might be in; you can solve this approximation with a simple 16 element lookup table. By discarding bits in the city's coordinates, you're approximating the solution, not finding the exact solution.
This is not just a triviality. The dynamic programming algorithm to solve subset sum runs in O(MN) time, where M is the number of integers, and N is the sum you're looking to achieve. Running subset sum on 1,000,000 numbers that you want to add up to 100 is going to run in milliseconds, but running that algorithm on 1,000,000 numbers that add up to 1,000,000,000 is going to take a while. (10,000,000 times as long) Subset sum is NP-complete, but it's only NP-complete because you're not talking about the value of the sum, you're talking about the number of bits it takes to represent the sum. One of the other problems in Karp's NP-completeness paper reduces to subset sum by summing up 1s or 0s shifted by i bits for each element in the input; so if there are 7 elements, the N for subset sum will be on the order of 2^7. If there are 1,000 elements, N for subset sum will be on the order of 2^1,000.
You can approximate subset sum by dividing every number by some constant. So if you want to know which integers of 3,4,5,6,7,8 sum to 12, you can divide everything by 3 and figure out which integers of 1,2,2,2,3,3 sum up to 4. (round up) If you were to take that 1,000 element problem, compute the sum to be some ludicrous integers on the order of 2^1,000, then divide everything by 2^980, and then solve the approximation in O(M * 2^20) time, what have you done? Well you've simply discarded 98% of the inputs. You haven't gained anything by reducing to subset sum and approximated the solution; you could have simply discarded all by 20 of the inputs and solved that with the brute force algorithm, whatever it is.
That's what this paper is doing by handwaving away the low order bits. They're saying you can solve TSP in O(m^k * n^j) time, where m is the number of cities, k and j and some arbitrary fixed constants, and n is the number of bits in the mantissa of your floating point scheme, ie, only if n is a small fixed constant. They've found an approximation of an NP-complete problem, which is something we already have in droves.