4 ms·

> A failure due to numerical difficulties of computers is not considered to be a counter-example. This seems to be something like an escape-hatch to reject any

> A failure due to numerical difficulties of computers is not considered to be a counter-example. This seems to be something like an escape-hatch to reject any counterexamples. > An issue attributable to numerical issues (for example, numerical stability and round-off errors) will not be considered as a basis for a valid claim of a counter-example. So if their algorithm never converges with your input, it's not a counterexample?

stonemetal12 4y ago
How so? It is a theoretical CS paper, what do hardware limitations have to do with it. >So if their algorithm never converges with your input, it's not a counterexample? No, if their algorithm never converges when calculated by hand it is a counterexample. If their algorithm never converges only because of rounding behavior in IEEE754 as implemented by Intel, then it isn't a counterexample.
- blamestross 4y ago
  Which means in order to collect you need to find a counterexample and solve it (a np hard problem) by hand. So yeah, there are easier ways for me to make $10k.
  - stonemetal12 4y ago
    Well you could computer generate counterexample by computer but hand verify that it isn't a hardware issue. Making 10k working for minimum wage is probably less effort and more likely to pay off.
    - ithinkso 4y ago
      The authors have this P=NP 'proof' for more than a decade. When the trisector comes[0] and offers you money for finding a mistake you are not going to see any money [0] http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf
- nwallin 4y ago
  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.

stonemetal12 4y ago

How so? It is a theoretical CS paper, what do hardware limitations have to do with it. >So if their algorithm never converges with your input, it's not a counterexample? No, if their algorithm never converges when calculated by hand it is a counterexample. If their algorithm never converges only because of rounding behavior in IEEE754 as implemented by Intel, then it isn't a counterexample.

blamestross 4y ago
Which means in order to collect you need to find a counterexample and solve it (a np hard problem) by hand. So yeah, there are easier ways for me to make $10k.
- stonemetal12 4y ago
  Well you could computer generate counterexample by computer but hand verify that it isn't a hardware issue. Making 10k working for minimum wage is probably less effort and more likely to pay off.
  - ithinkso 4y ago
    The authors have this P=NP 'proof' for more than a decade. When the trisector comes[0] and offers you money for finding a mistake you are not going to see any money [0] http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf http://web.mst.edu/~lmhall/WhatToDoWhenTrisectorComes.pdf
nwallin 4y ago
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.