5 ms·

>Unfortunately that means exactly nothing. The whole point is that for many (perhaps most) problems, the proportion of hard instances gets vanishingly small, an

>Unfortunately that means exactly nothing. The whole point is that for many (perhaps most) problems, the proportion of hard instances gets vanishingly small, and yet those are the ones that we often need to solve. Showing a sub-exponential trend for randomly chosen instances, or worse, instances he's chosen to show you, is no evidence at all. I wouldn't say exactly nothing. If no one can present an algorithm than can do at least as good on the same instances...that's interesting. He did not choose the instances. They were generated using multiple calls to a built-in pseudo-random function. The instances were generated when he requested an instance and the timer started when the instances were transmitted to him. The timer was stopped when a response was received and the response was then verified. He never submitted an incorrect answer. [Aside: There is a particular web page of a university professor that lists a smallish subset sum problem and claims that the naive algorithm would take some 10^large_number years to find the answer. His algorithm solves that particular instance in some very short period of time (seconds or less I believe). Is that particular instance "hard"? I don't know. Apparently not. He likes to use that instance as an example of his algorithm solving a "hard" problem. My problem is that I don't know how to verify if an instance is hard (or if such an analysis is even possible/valid). My instincts say that it very much depends on the "density of solutions" in the particular instance. Maybe that instance has lots of solutions and so a random walk will easily find one? On the other hand, maybe there is a limit to the number of solutions that can exist in a well-formed instance?] While I do not understand his entire proof (and I do believe he has intentionally withheld a portion of the proof [and certainly a key piece of the algorithm (if it exists)]), he does point to some interesting things (such as an apparent fractal pattern in the sum of all sets in the powerset of a set of integers). He claims a function that provides an ordering over the sums of the sets in the powerset, which can apparently be computed on-demand in polynomial time of the original set. A binary search is then applied over the ordering. In my own theory, it seems like it could be possible; after all, there isn't an exponential number of items, only combinations. >The whole point Sorry, the whole point of what? NP-Completeness?

ColinWright 11y ago
>> Showing a sub-exponential trend for >> randomly chosen instances ... is no >> evidence at all. > If no one can present an algorithm > than can do at least as good on the > same instances...that's interesting. It proves nothing about whether it's a polynomial algorithm, or even a sub-exponential algorithm. > He did not choose the instances. They > were generated using multiple calls > to a built-in pseudo-random function. Even worse - you know nothing about how the instances were created, or whether they are supposed to be hard. Does this magic function claim to produce known hard instances? > ... a particular web page ... that > lists a smallish subset sum problem > ... claims that the naive algorithm > would take some 10^large_number years > to find the answer. His algorithm > solves that particular instance in > some very short period of time ... > Is that particular instance "hard"? > I don't know. Apparently not. Indeed - apparently not. This entire discussion is running in circles. You keep feeding me small pieces of information, one piece at a time, and it's not adding up to anything convincing. At this point I feel the discussion is going nowhere. > ... I don't know how to verify if an > instance is hard ... Largely speaking no one does, which is why we require proofs of worst case running times. Proofs are difficult, and to present a proof requires full disclosure of the entire algorithm. To expend effort on such a proof some evidence is required to make it likely to be worthwhile. To say: I found this place that gives me instances, and I solve them all quickly. ... is unconvincing. > My instincts say that it very much > depends on the "density of solutions" > in the particular instance. Maybe > that instance has lots of solutions > and so a random walk will easily find > one? Or maybe every obvious choice you make is the right one. Hard instances are hard when you have to make choices early, and you only find out much later that the choice you made was wrong. That's what creates the exponential search space. > On the other hand, maybe there is a > limit to the number of solutions that > can exist in a well-formed instance? Number of solutions to an instance is not usually a good measure, unless there are exponentially many. Usually there aren't. > While I do not understand his entire > proof (and I do believe he has > intentionally withheld a portion of > the proof [and certainly a key piece > of the algorithm (if it exists)]), Making it impossible to provide an effective evaluation ... > ... he does point to some interesting > things (such as an apparent fractal > pattern in the sum of all sets in the > powerset of a set of integers). That seems to be a meaningless comment without more information. > He claims a function that provides an > ordering over the sums of the sets in > the powerset, which can apparently be > computed on-demand in polynomial time > of the original set. A binary search > is then applied over the ordering. Again, doesn't seem to mean much. Feels a lot like simple dynamic programming. > In my own theory, it seems like it > could be possible; after all, there > isn't an exponential number of items, > only combinations. But it's the combinations that need to be searched, not simply the items. There are only a linear number of vertices in graphs, and at most a quadratic number of edges, and yet that's NP-Complete. >>>> But you know someone who claims to be >>>> able to solve subset-sum problems quickly. >>> ... He also ran through many thousands >>> of problem instances ... with varying >>> parameters ... it did appear that there >>> was a sub-exponential trend ... >> Unfortunately that means exactly nothing. >> The whole point is that for many (perhaps >> most) problems, the proportion of hard >> instances gets vanishingly small, > Sorry, the whole point of what? NP-Completeness? No, the whole point of my comments to you. Let me summarize: * You know someone who claims to have a sub-exponential solution to the Subset Sum problem. * The evidence provided is that over a large collection of instances, the solution time seems to be sub-exponential. * The difficulty is that to be a solution to P=NP you need an algorithm that runs sub-exponentially on all cases. * Most instances are easy, but you/he need to show that the algorithm runs sub-exponentially on all instances, not just the easy ones. * The whole point of all my comments is that claiming sub-exponential running time on specific examples/instances is no proof, and poor evidence.
- jsprogrammer 11y ago
  >* >* >* I generally agree with all of that and I don't think I have made a claim that contradicts your summary. I haven't re-read this entire thread in awhile, but I believe you came into this seeking a clarification to what I was asking on a different thread. The reason it might seem like I am only piecing you pieces of information is that I am just responding to your questions and points as I perceive them to be related to my memory of what that thread was about. If the search space is finite for problems of a certain length [it is], you may be able to uniformly sample from the instance space of a given problem and attempt to derive a statistical characterization of a given algorithm. I do not now if iteratively sampling integers from a uniform distribution is the "best" way to search the space, but it seems like it would give you a reasonable/interesting map of a particular area. The only intent of the exercise was to explore. To a part of your point: >Most instances are easy, but you/he need to show that the algorithm runs sub-exponentially on all instances, not just the easy ones. Absolutely, a proof requires showing all instances can be solved by a single [deterministic (non-non-deterministic) [etc....insert your own word here]] algorithm in polynomial time of the length of the instance (Edit: On second read, I might change this to 'problem' [which may need to be distinguished from Problem]). I have not seen that, so I do not claim or claim to know of any P=NP proof. >The whole point of all my comments is that claiming sub-exponential running time on specific examples/instances is no proof, and poor evidence. The point of my question was to get instances (simulated or real) to feed to this person's algorithm to see it could actually solve problems people want solved quicker/much quicker than competing algorithms. Additionally, I am interested in the topic more generally and was looking for speculation on which problems (and instances) might be the most "beneficial" (as defined in our conversation) to solve (ie. give to a hypothesized solver that you trust to solve in a given polynomial time of the length of the problem). Since it is impractical to search the entire instance space for problems of larger than some smallish length, you may test an algorithm with a specifically [Aside: I believe this may be implied by 'algorithm'...though the halting problem may prevent such arbitrary analysis of running times...] claimed polynomial limit on the running time. Any (hypothesized) P=NP exploiting solver would (speculative) make a polynomial-time running claim that could be tested. I don't know what running-time limits he has put on his algorithm. It is one of the reasons I am skeptical of his proof.

ColinWright 11y ago

>> Showing a sub-exponential trend for >> randomly chosen instances ... is no >> evidence at all. > If no one can present an algorithm > than can do at least as good on the > same instances...that's interesting. It proves nothing about whether it's a polynomial algorithm, or even a sub-exponential algorithm. > He did not choose the instances. They > were generated using multiple calls > to a built-in pseudo-random function. Even worse - you know nothing about how the instances were created, or whether they are supposed to be hard. Does this magic function claim to produce known hard instances? > ... a particular web page ... that > lists a smallish subset sum problem > ... claims that the naive algorithm > would take some 10^large_number years > to find the answer. His algorithm > solves that particular instance in > some very short period of time ... > Is that particular instance "hard"? > I don't know. Apparently not. Indeed - apparently not. This entire discussion is running in circles. You keep feeding me small pieces of information, one piece at a time, and it's not adding up to anything convincing. At this point I feel the discussion is going nowhere. > ... I don't know how to verify if an > instance is hard ... Largely speaking no one does, which is why we require proofs of worst case running times. Proofs are difficult, and to present a proof requires full disclosure of the entire algorithm. To expend effort on such a proof some evidence is required to make it likely to be worthwhile. To say: I found this place that gives me instances, and I solve them all quickly. ... is unconvincing. > My instincts say that it very much > depends on the "density of solutions" > in the particular instance. Maybe > that instance has lots of solutions > and so a random walk will easily find > one? Or maybe every obvious choice you make is the right one. Hard instances are hard when you have to make choices early, and you only find out much later that the choice you made was wrong. That's what creates the exponential search space. > On the other hand, maybe there is a > limit to the number of solutions that > can exist in a well-formed instance? Number of solutions to an instance is not usually a good measure, unless there are exponentially many. Usually there aren't. > While I do not understand his entire > proof (and I do believe he has > intentionally withheld a portion of > the proof [and certainly a key piece > of the algorithm (if it exists)]), Making it impossible to provide an effective evaluation ... > ... he does point to some interesting > things (such as an apparent fractal > pattern in the sum of all sets in the > powerset of a set of integers). That seems to be a meaningless comment without more information. > He claims a function that provides an > ordering over the sums of the sets in > the powerset, which can apparently be > computed on-demand in polynomial time > of the original set. A binary search > is then applied over the ordering. Again, doesn't seem to mean much. Feels a lot like simple dynamic programming. > In my own theory, it seems like it > could be possible; after all, there > isn't an exponential number of items, > only combinations. But it's the combinations that need to be searched, not simply the items. There are only a linear number of vertices in graphs, and at most a quadratic number of edges, and yet that's NP-Complete. >>>> But you know someone who claims to be >>>> able to solve subset-sum problems quickly. >>> ... He also ran through many thousands >>> of problem instances ... with varying >>> parameters ... it did appear that there >>> was a sub-exponential trend ... >> Unfortunately that means exactly nothing. >> The whole point is that for many (perhaps >> most) problems, the proportion of hard >> instances gets vanishingly small, > Sorry, the whole point of what? NP-Completeness? No, the whole point of my comments to you. Let me summarize: * You know someone who claims to have a sub-exponential solution to the Subset Sum problem. * The evidence provided is that over a large collection of instances, the solution time seems to be sub-exponential. * The difficulty is that to be a solution to P=NP you need an algorithm that runs sub-exponentially on all cases. * Most instances are easy, but you/he need to show that the algorithm runs sub-exponentially on all instances, not just the easy ones. * The whole point of all my comments is that claiming sub-exponential running time on specific examples/instances is no proof, and poor evidence.

jsprogrammer 11y ago
>* >* >* I generally agree with all of that and I don't think I have made a claim that contradicts your summary. I haven't re-read this entire thread in awhile, but I believe you came into this seeking a clarification to what I was asking on a different thread. The reason it might seem like I am only piecing you pieces of information is that I am just responding to your questions and points as I perceive them to be related to my memory of what that thread was about. If the search space is finite for problems of a certain length [it is], you may be able to uniformly sample from the instance space of a given problem and attempt to derive a statistical characterization of a given algorithm. I do not now if iteratively sampling integers from a uniform distribution is the "best" way to search the space, but it seems like it would give you a reasonable/interesting map of a particular area. The only intent of the exercise was to explore. To a part of your point: >Most instances are easy, but you/he need to show that the algorithm runs sub-exponentially on all instances, not just the easy ones. Absolutely, a proof requires showing all instances can be solved by a single [deterministic (non-non-deterministic) [etc....insert your own word here]] algorithm in polynomial time of the length of the instance (Edit: On second read, I might change this to 'problem' [which may need to be distinguished from Problem]). I have not seen that, so I do not claim or claim to know of any P=NP proof. >The whole point of all my comments is that claiming sub-exponential running time on specific examples/instances is no proof, and poor evidence. The point of my question was to get instances (simulated or real) to feed to this person's algorithm to see it could actually solve problems people want solved quicker/much quicker than competing algorithms. Additionally, I am interested in the topic more generally and was looking for speculation on which problems (and instances) might be the most "beneficial" (as defined in our conversation) to solve (ie. give to a hypothesized solver that you trust to solve in a given polynomial time of the length of the problem). Since it is impractical to search the entire instance space for problems of larger than some smallish length, you may test an algorithm with a specifically [Aside: I believe this may be implied by 'algorithm'...though the halting problem may prevent such arbitrary analysis of running times...] claimed polynomial limit on the running time. Any (hypothesized) P=NP exploiting solver would (speculative) make a polynomial-time running claim that could be tested. I don't know what running-time limits he has put on his algorithm. It is one of the reasons I am skeptical of his proof.