3 ms·

>* >* >* 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 awhil

>* >* >* 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
> 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'm not sure what you're referring to about the search space, but the detail isn't important - what you say here is not the case. When dealing with NPC problems, the instances form a landscape that's not like rolling hills, but like a mesa with wells and flagpoles. Most of the time you wander around, broadly speaking at the same level, and then you might, if you're unbelievably lucky, fall down a well, or find a flagpole to climb. But this becomes implausibly difficult as the sizes get properly big. Sampling the space just doesn't work. > I do not know 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. Doesn't work. Our intuition tends to be drawn from our experience in three dimensions, but it just doesn't work in higher dimensions. And with NPC problems we are in huge numbers of dimensions - thousands, tens of thousands. Here's a link: http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres >> 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 ... Yes, I think I finally understand your question. My intention is to blog the question using my working and a hypothetical context. Before I make it public and I can get your comments, but you still haven't given me an email address. If you don't, I'll have to do it here. > 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 ... 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 think that makes sense, so obviously I've missed something. I don't understand what you mean by a "P=NP exploiting solver". I don't see how a solver would exploit P=NP - that doesn't make sense to me. > 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. This doesn't make sense to me either. In a proof one shows that the time taken is always less than some limit, regardless of the input. One doesn't talk about having a running-time limit - that seems irrelevant to the entire question. If you send me an email I'll point you at my post when I write it and before I publish it, so you can comment.

ColinWright 11y ago

> 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'm not sure what you're referring to about the search space, but the detail isn't important - what you say here is not the case. When dealing with NPC problems, the instances form a landscape that's not like rolling hills, but like a mesa with wells and flagpoles. Most of the time you wander around, broadly speaking at the same level, and then you might, if you're unbelievably lucky, fall down a well, or find a flagpole to climb. But this becomes implausibly difficult as the sizes get properly big. Sampling the space just doesn't work. > I do not know 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. Doesn't work. Our intuition tends to be drawn from our experience in three dimensions, but it just doesn't work in higher dimensions. And with NPC problems we are in huge numbers of dimensions - thousands, tens of thousands. Here's a link: http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres >> 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 ... Yes, I think I finally understand your question. My intention is to blog the question using my working and a hypothetical context. Before I make it public and I can get your comments, but you still haven't given me an email address. If you don't, I'll have to do it here. > 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 ... 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 think that makes sense, so obviously I've missed something. I don't understand what you mean by a "P=NP exploiting solver". I don't see how a solver would exploit P=NP - that doesn't make sense to me. > 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. This doesn't make sense to me either. In a proof one shows that the time taken is always less than some limit, regardless of the input. One doesn't talk about having a running-time limit - that seems irrelevant to the entire question. If you send me an email I'll point you at my post when I write it and before I publish it, so you can comment.