9 ms·

> Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false. Is th

> Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false. Is this the crux of the post? That seems like an extremely crap reason to believe a mathematical theorem. What am I missing? I also don't find his heuristic convincing -- to the point his description is making me question if P=NP is actually possible after all: a close complex border that seems to yield increasing numbers of "close calls" sounds exactly like the situation where there's a lurking, sparse class of "touches" that we haven't thought of, particularly when under 100 years of research has been put into the topic.

nl 9y ago
That seems like an extremely crap reason to believe a mathematical theorem. What am I missing? What's the alternative? As I see it, the possible ways to think about it are as follows: 1) You must think of it as 50/50 possibility of being true until an absolute proof is found. 2) You look at places where it could fail, and if it passes then you update the likelihood based on that. To me (and as this post argues) it makes sense to follow (2). Not only is it more useful practically (you can use that assumption to solve other things, conditional on it being true) but also it reflects the reality of the world. Even if it turns out not to be true in every case it is clear that in the majority of cases it is true. Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class. close complex border that seems to yield increasing numbers of "close calls" sounds exactly like the situation where there's a lurking, sparse class of "touches" that we haven't thought of That's not really how it works though. If it keeps happening and those classes don't touch, then it typically means they aren't as close as they seem (ie, there is an extra dimension in which they are a long way apart). In this case it seems like the P/NP divide is actually a thing which means things which appear close actually aren't, so if you analyze them in that space they don't appear close together at all.
- Filligree 9y ago
  > Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class. Any NP-complete problem reduces to any other, so if P=NP for any of them then it's true in general. Some more efficiently than others, of course.
  - deleted 9y ago
    [deleted]
  - nl 9y ago
    This is a fair point. I guess my only response would be that some of the complexity classes in "some more efficiently than others, of course" might be impractical even if they are theoretically possible.
    - Filligree 9y ago
      Which might be the saving grace should the equality turn out to be true, given the sheer number of scary-powerful algorithms that happen to be NP-complete. Certainly it'd be convenient if they were solvable, but... probably not safe, you understand? Not really relevant here, though.
- SomeStupidPoint 9y ago
  What's the argument here, though? When we find a single bridge, all the complexity classes change, so we can only really divide the problems here into "ones we've found polynomial time solutions for" and "ones we haven't". There may be something interesting about the ones we havent -- or we just didn't think of something obvious/a lot of special cases with high degree polynomials. It's worth mentioning the near collisions happen in the low-dimensionality region of the border -- which doesn't have the same separating forecast, as it becomes easier to touch in higher dimensions. We can think of a sphere and a cube -- in low dimensions, a sphere lies inside of a cube; in higher dimensions, the surface bulges past the sides. You just don't see it until something like the 17th dimension. (Similarly, knot theory explodes with complexity in higher dimensions.) Taking a "scientific approach" to asymptotic problems just makes the CS people advocating it seem vaguely hacky, since they're not even advancing a proper density argument -- it's just such a low-dimensional, poorly bounded argument that it's clear they didn't make a real calculation, they tried to dress up personal feelings in science.
closed 9y ago
Hmm.. good point. It'd be interesting to think of examples where something with a "complex border" turned out true, and examples where it turned out false. (On a side not, I love this kind of scientific approach to believing unproved theorems, and Polya has a lot of thoughts on the topic)
rocqua 9y ago
The argument isn't that P≠NP is true because it has passed tests. The argument is that it seems to be true because it has passed tests. Specifically, it seems much more likely to be true than false. Consider this. You have to bet on either P=NP or P≠NP. Where do you put your money. That is the question we are trying to answer.
- SomeStupidPoint 9y ago
  My point is that his heuristic has dropped my expected value for betting on P != NP, because his argument is one that suggests we will find a class, not that we won't. His description of "passing tests" actually sounds like the buildup of stress before breakage, where many near-faults are generated. I'm less confident of the resolution post reading that -- so it seems extremely weird to present as evidence that P != NP, as it shifted my beliefs the exact opposite way.
  - naasking 9y ago
    Then perhaps you haven't properly understood the argument he's making. Your "stress before breakage" argument is literally the gambler's fallacy.
    - SomeStupidPoint 9y ago
      > Your "stress before breakage" argument is literally the gambler's fallacy. It's not even anything close: the gambler's fallacy requires that the events you're trying to relate are uncorrelated. The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions. So -- the fallacy requires you be trying to correlate uncorrelated things; I am not. I'm correlating things that are going to be correlated because of how the spaces are constructed.
      - naasking 9y ago
        > The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions. Is it? This strikes me as pretty contentious.
ubernostrum 9y ago
Mathematics is full of things which show asymptotic behavior, so I'm not sure why the ability to find points where two things are arbitrarily "close" to each other would be read as indicating the likeliehood of a point where they "touch".
postramus 9y ago
His earlier post (linked from this) has stronger reasons. I think it’s advisable to keep an open mind on the issue, and not simply on the actual question itself; it would not be surprising to me if the solution comes from something like adopting a different framework. For example, time bounds and complexity classes smell a lot like conservation laws: “transforming such and such arrangement into such and such arrangement requires at least this much computation.” That said, it’s possible (a) we’re currently failing to consider some “term”, (b) generally ignoring this term doesn’t cause problems when proving lower bounds but (c) the complex border and your “sparse touches” correspond to situations where the missing term plays a more significant role. That’s a case where P probably isn’t equal to NP but keeping an open mind at least leads in more interesting directions, imho. I also think people don’t take seriously the possibility of P being equal to NP but with intrinsically high degree. I say this not to be cute—“what if p is np but still de-facto intractable?”—but because I don’t think anyone has a great intuition for, say, what kinds of algorithms have polynomial solutions of minimum degree, say, 8...at least not in the same way we have good intuition for which algorithms are linear, nlogn, n^2, n^3, and so on. It’s hard for me, at least, to feel overly confident in the “we’ve been working on finding a fast algorithm for seventy years and gotten nowhere” when our algorithmic intuition vis-a-vis higher polynomial degree seems so under-developed. Even if you don’t consider it likely that p equals np, you can still follow this line of thought and consider the possibility that these “sparse touches” may be cases where the slippery problems like graph isomorphism (etc) correspond to problems with polynomial running times of (unexpectedly) high degree...and thus we keep finding these sparse touches along a seemingly-complex border because we don’t yet have a solid intuition for the capabilities of polynomial algorithms of high degree. And so on and so forth. P probably isn’t NP but being dogmatic about it is neither fun nor interesting.
- SomeStupidPoint 9y ago
  You touch on something I had thought, but not said: His argument seems to be "well, the border doesnt touch using under degree 100 polynomials, so it must never touch!" I'm disinclined to believe that order 10^374738393874 polynomials can be accurately forecast by order under 100 polynomials, and suspect that portion of the border simply hasn't been examined at all or only in the most basic cases.
jcranmer 9y ago
The "idiot's explanation of P=NP" that refers to "easy" or "practical" is at this point fairly well established as disproven. It's possible for P=NP, but for that to happen, the algorithm pretty much has to be completely impractical. To summarize the argument in more general terms: the class of algorithms in P is those where you can derive some global property in terms of increment local decisions. For example, building the shortest path between two nodes in a graph can be done by always picking the closest node. By contrast, NP-hard algorithms have the problem that incremental local decisions don't let that happen: you might need to recolor an entire optimally-colored subgraph to admit a new node. Furthermore, we know from research that there tends to be a very sharp transition from P to NP-hard in terms of transformation, where relaxing a single condition goes straight from P to NP-hard without any intermediate "we don't know where there is" space. This tends to suggest that it's not really so much a question of problems being P or NP, but rather of instances being intrinsically easy to hard. The question of P=NP then is really about whether these hard instances are really exponentially hard, or can we embed them into a simpler instance using some combinatorial construct that merely makes it look exponentially hard. So it's still possible for P=NP, but the practical question of "will we get an efficient, guaranteed for all instances, solution to these problems?" is answered in the negative. When you do the combinatorial embeddings to make the polynomial time algorithms work, you end up getting constants that look like 3^2^2^4, and there's no way to shrink those constants to practical ones.
- SomeStupidPoint 9y ago
  ....Duh? But it's absolutely insane to take the impossibility of low-constant, low-degree embedding as evidence as a general lack, given the rich structure of "large" numbers. Which is what it's being used as in this post.

nl 9y ago

That seems like an extremely crap reason to believe a mathematical theorem. What am I missing? What's the alternative? As I see it, the possible ways to think about it are as follows: 1) You must think of it as 50/50 possibility of being true until an absolute proof is found. 2) You look at places where it could fail, and if it passes then you update the likelihood based on that. To me (and as this post argues) it makes sense to follow (2). Not only is it more useful practically (you can use that assumption to solve other things, conditional on it being true) but also it reflects the reality of the world. Even if it turns out not to be true in every case it is clear that in the majority of cases it is true. Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class. close complex border that seems to yield increasing numbers of "close calls" sounds exactly like the situation where there's a lurking, sparse class of "touches" that we haven't thought of That's not really how it works though. If it keeps happening and those classes don't touch, then it typically means they aren't as close as they seem (ie, there is an extra dimension in which they are a long way apart). In this case it seems like the P/NP divide is actually a thing which means things which appear close actually aren't, so if you analyze them in that space they don't appear close together at all.

Filligree 9y ago
> Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class. Any NP-complete problem reduces to any other, so if P=NP for any of them then it's true in general. Some more efficiently than others, of course.
- deleted 9y ago
  [deleted]
- nl 9y ago
  This is a fair point. I guess my only response would be that some of the complexity classes in "some more efficiently than others, of course" might be impractical even if they are theoretically possible.
  - Filligree 9y ago
    Which might be the saving grace should the equality turn out to be true, given the sheer number of scary-powerful algorithms that happen to be NP-complete. Certainly it'd be convenient if they were solvable, but... probably not safe, you understand? Not really relevant here, though.
SomeStupidPoint 9y ago
What's the argument here, though? When we find a single bridge, all the complexity classes change, so we can only really divide the problems here into "ones we've found polynomial time solutions for" and "ones we haven't". There may be something interesting about the ones we havent -- or we just didn't think of something obvious/a lot of special cases with high degree polynomials. It's worth mentioning the near collisions happen in the low-dimensionality region of the border -- which doesn't have the same separating forecast, as it becomes easier to touch in higher dimensions. We can think of a sphere and a cube -- in low dimensions, a sphere lies inside of a cube; in higher dimensions, the surface bulges past the sides. You just don't see it until something like the 17th dimension. (Similarly, knot theory explodes with complexity in higher dimensions.) Taking a "scientific approach" to asymptotic problems just makes the CS people advocating it seem vaguely hacky, since they're not even advancing a proper density argument -- it's just such a low-dimensional, poorly bounded argument that it's clear they didn't make a real calculation, they tried to dress up personal feelings in science.

closed 9y ago

Hmm.. good point. It'd be interesting to think of examples where something with a "complex border" turned out true, and examples where it turned out false. (On a side not, I love this kind of scientific approach to believing unproved theorems, and Polya has a lot of thoughts on the topic)

rocqua 9y ago

The argument isn't that P≠NP is true because it has passed tests. The argument is that it seems to be true because it has passed tests. Specifically, it seems much more likely to be true than false. Consider this. You have to bet on either P=NP or P≠NP. Where do you put your money. That is the question we are trying to answer.

SomeStupidPoint 9y ago
My point is that his heuristic has dropped my expected value for betting on P != NP, because his argument is one that suggests we will find a class, not that we won't. His description of "passing tests" actually sounds like the buildup of stress before breakage, where many near-faults are generated. I'm less confident of the resolution post reading that -- so it seems extremely weird to present as evidence that P != NP, as it shifted my beliefs the exact opposite way.
- naasking 9y ago
  Then perhaps you haven't properly understood the argument he's making. Your "stress before breakage" argument is literally the gambler's fallacy.
  - SomeStupidPoint 9y ago
    > Your "stress before breakage" argument is literally the gambler's fallacy. It's not even anything close: the gambler's fallacy requires that the events you're trying to relate are uncorrelated. The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions. So -- the fallacy requires you be trying to correlate uncorrelated things; I am not. I'm correlating things that are going to be correlated because of how the spaces are constructed.
    - naasking 9y ago
      > The logical structure of P vs NP is anything but uncorrelated along its surface, and a rough surface along the low-dimensionality region is a good indication of a rough surface along the higher-dimensionality regions. Is it? This strikes me as pretty contentious.

ubernostrum 9y ago

Mathematics is full of things which show asymptotic behavior, so I'm not sure why the ability to find points where two things are arbitrarily "close" to each other would be read as indicating the likeliehood of a point where they "touch".

postramus 9y ago

His earlier post (linked from this) has stronger reasons. I think it’s advisable to keep an open mind on the issue, and not simply on the actual question itself; it would not be surprising to me if the solution comes from something like adopting a different framework. For example, time bounds and complexity classes smell a lot like conservation laws: “transforming such and such arrangement into such and such arrangement requires at least this much computation.” That said, it’s possible (a) we’re currently failing to consider some “term”, (b) generally ignoring this term doesn’t cause problems when proving lower bounds but (c) the complex border and your “sparse touches” correspond to situations where the missing term plays a more significant role. That’s a case where P probably isn’t equal to NP but keeping an open mind at least leads in more interesting directions, imho. I also think people don’t take seriously the possibility of P being equal to NP but with intrinsically high degree. I say this not to be cute—“what if p is np but still de-facto intractable?”—but because I don’t think anyone has a great intuition for, say, what kinds of algorithms have polynomial solutions of minimum degree, say, 8...at least not in the same way we have good intuition for which algorithms are linear, nlogn, n^2, n^3, and so on. It’s hard for me, at least, to feel overly confident in the “we’ve been working on finding a fast algorithm for seventy years and gotten nowhere” when our algorithmic intuition vis-a-vis higher polynomial degree seems so under-developed. Even if you don’t consider it likely that p equals np, you can still follow this line of thought and consider the possibility that these “sparse touches” may be cases where the slippery problems like graph isomorphism (etc) correspond to problems with polynomial running times of (unexpectedly) high degree...and thus we keep finding these sparse touches along a seemingly-complex border because we don’t yet have a solid intuition for the capabilities of polynomial algorithms of high degree. And so on and so forth. P probably isn’t NP but being dogmatic about it is neither fun nor interesting.

SomeStupidPoint 9y ago
You touch on something I had thought, but not said: His argument seems to be "well, the border doesnt touch using under degree 100 polynomials, so it must never touch!" I'm disinclined to believe that order 10^374738393874 polynomials can be accurately forecast by order under 100 polynomials, and suspect that portion of the border simply hasn't been examined at all or only in the most basic cases.

jcranmer 9y ago

The "idiot's explanation of P=NP" that refers to "easy" or "practical" is at this point fairly well established as disproven. It's possible for P=NP, but for that to happen, the algorithm pretty much has to be completely impractical. To summarize the argument in more general terms: the class of algorithms in P is those where you can derive some global property in terms of increment local decisions. For example, building the shortest path between two nodes in a graph can be done by always picking the closest node. By contrast, NP-hard algorithms have the problem that incremental local decisions don't let that happen: you might need to recolor an entire optimally-colored subgraph to admit a new node. Furthermore, we know from research that there tends to be a very sharp transition from P to NP-hard in terms of transformation, where relaxing a single condition goes straight from P to NP-hard without any intermediate "we don't know where there is" space. This tends to suggest that it's not really so much a question of problems being P or NP, but rather of instances being intrinsically easy to hard. The question of P=NP then is really about whether these hard instances are really exponentially hard, or can we embed them into a simpler instance using some combinatorial construct that merely makes it look exponentially hard. So it's still possible for P=NP, but the practical question of "will we get an efficient, guaranteed for all instances, solution to these problems?" is answered in the negative. When you do the combinatorial embeddings to make the polynomial time algorithms work, you end up getting constants that look like 3^2^2^4, and there's no way to shrink those constants to practical ones.

SomeStupidPoint 9y ago
....Duh? But it's absolutely insane to take the impossibility of low-constant, low-degree embedding as evidence as a general lack, given the rich structure of "large" numbers. Which is what it's being used as in this post.