6 ms·

I've been convinced P!=NP ever since I started studying semigroup lower bounds. Even black box group membership is exponential in the largest prime less than or

by crb002 9y ago

I've been convinced P!=NP ever since I started studying semigroup lower bounds. Even black box group membership is exponential in the largest prime less than or equal to N. https://oeis.org/A186202 https://oeis.org/A186202

jmcgough 9y ago
P!=NP seems to be the general sentiment, though we're still waiting on the proof :)
- tachyonbeam 9y ago
  I share the same sentiment, but I think it could be that P!=NP is an unprovable statement. Could be that there's something fundamental about the nature of computing which makes it impossible to prove or disprove it.
  - sacheendra 9y ago
    Maybe that could be a thing to prove. Is it possible to prove that something is not provable?
    - jlebar 9y ago
      See http://www.scottaaronson.com/papers/indep.ps http://www.scottaaronson.com/papers/indep.ps
    - emmab 9y ago
      > Is it possible to prove that something is not provable? It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent...
    - infogulch 9y ago
      In general yes. [1] I don't know about PvNP [1]: https://math.stackexchange.com/questions/2027182/how-do-we-prove-that-something-is-unprovable https://math.stackexchange.com/questions/2027182/how-do-we-p...
    - auggierose 9y ago
      Yep. That's what Gödel did.
  - emmab 9y ago
    Something is only unprovable wrt an axiom set. You can add new axioms to an existing axiom set that can be semi-decidably proved inconsistent given the rest of the axiom set. https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... For a theory of how to choose an axiom set probabilistically, see: https://intelligence.org/2016/09/12/new-paper-logical-induction/ https://intelligence.org/2016/09/12/new-paper-logical-induct...
    - Houshalter 9y ago
      You can't just add arbitrary axioms. It's entirely possible to have a statement that's unprovable with any axioms mathematicians would consider reasonable.
      - emmab 9y ago
        An axiom can be wrong wrt the standard model for some first-order theory: http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers/ http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers... But, demonstrating an axiom is inconsistent with the standard model of peano arithmetic or ZFC is in the general case uncomputable. For example, an axiom that claims some program halts when it does not actually halt cannot in general be proved to be inconsistent wrt the standard model, because otherwise one could decide the halting problem.
  - sjg007 9y ago
    What if it is not computable?
  - DonbunEf7 9y ago
    I used to think this, too, but Aaronson changed my mind with the observation in [0] that, if P != NP is independent, then it would necessarily imply a lot of what we would demand from a constructive P = NP proof. In particular, we could get some pretty hilarious improvements on those exponents in NP-complete algorithms, to the point where they become tractable for day-to-day computing. There is a sense in which any complexity class which is self-low is "physical", or analogous to machines which we might build by hand with modular designs. A self-low class doesn't gain any additional power when relativized with itself as an oracle, and this directly corresponds to building a physical machine out of smaller machine modules. We know that P is self-low. It seems that the universe insists that either we are able to build machines which tractably solve NP-complete problems, or not, but there is no in-between position. [0] http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf p28
  - tgflynn 9y ago
    I don't see how it could be unprovable. As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity. You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n. Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n. This is now a question about a finite set which has a definite answer which could, in principle, be determined by enumerating all possible algorithms (represented, for example, by boolean circuits with some large size bound) for a particular NP complete problem for problem sizes up to n. Of course this would probably take many times the lifetime of the universe to actually do, but it could be done in principle. So the question of how the minimum circuit size which solves an NP complete problem scales with n has a definite answer.
    - contravariant 9y ago
      >enumerating all possible algorithms [...] for problem sizes up to n. Please keep in mind that this includes an algorithm that has precomputed all possible solutions and retrieves their value from a list. In fact I find it hard to say for certain that you can't for instance assume the existence of an algorithm that calculates the answers to some NP problem in constant time, but which takes an amount of time that can't be proven to be smaller than any other number. This would lead to a situation where P != NP may not be provable.
    - ColinWright 9y ago
      > I don't see how it could be unprovable. It's quite plausible that it's unprovable, although you would have to be specific about the axiom system you're using. > As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity. It does. > You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n. No, you can't. You don't know how large that n has to be, so you have to prove it for arbitrarily large n, and that's the "infinity" that you're dismissing. > Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n. So you've changed the question to one that can be proven. The original question might still be unprovable. So I don't see how your comment really makes any sense at all. Perhaps you could be a little more precise.
  - CJefferson 9y ago
    I don't think it's impossible to prove, I think we just aren't yet good at proving it. One reason I believe P!=NP is I can imagine what a proof of P=NP would look like -- just write a C program that solves SAT or Sudoku or something, in polynomial time, and prove it's correctness and execution time. There are tens of thousands of papers which do that, for various problems. I can't really imagine what a proof of P!=NP would look like, proving something doesn't exist is extremely hard, particularly because for any particular instance of an NP problem, there is a problem which solves it "by luck".
    - chx 9y ago
      Even if it'll be a constructive proof, it doesn't mean you could actually write the C program. It'll be like, here are the steps to construct an algorithm for this NP complete problem and then the number of steps itself is bound by n^(absurdly large number) and then prove the complexity is bound by n^(another absurdly large number). It will have zero practical consequences.
  - rlanday 9y ago
    There are many, many things that are most likely provable that have not been proven yet. Fermat's Last Theorem went 358 years before it was finally proven. Theoretical computer science is a very young field by comparison.
    - Houshalter 9y ago
      Years is a bad measure to use. The number of mathematicians has grown exponentially over the last 400 years. Both because of population growth and the Flynn effect, and because our society is a lot richer and we spend more on mathematical research.
      - rlanday 9y ago
        On the other hand, can nine women have a baby in a month?
- mixedmath 9y ago
  I think it's interesting that Knuth came to believe that P=NP. See question 17 and its response in this interview with him [1]. [1]: http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858
padobson 9y ago
Yeah, proving it is not going to be much of a game changer. Most everyone already assumes it's true. But if someone were to prove the opposite, the entire technology world would shift dramatically, so it will certainly help to have a proof for this.
- Guvante 9y ago
  That is assuming the constant end up being in the realm of reasonable. `O(2^N)` and `O(N^1000)` are no different for any useful values of `N`.
- rickduggan 9y ago
  Wouldn't someone proving it true be a game changer in that it would preclude the ability of anyone to prove the opposite?
danbruc 9y ago
I have been convinced that P==NP since my first exposure to the topic in university. There are NP complete problems where I can really not imagine how they could be solved quickly, but vertex three coloring just looks so doable to me by some informal intuitive arguments. In another life I would devote my life to fleshing out the argument and proving P==NP. Or at least learn where my intuitive argument fails.
- artosispylon 9y ago
  By definition, each NP-complete problem is provably as hard as another though. Graph coloring can be reduced in polynomial time to every NP-C problem. It doesn't really make sense to me that one problem can just "look so doable" when they're really just the same problems.
  - danbruc 9y ago
    They are of course all reducible to each other but that doesn't necessarily mean that they are all equally hard to attack. That's very common in mathematics where reformulating the problem can make the relevant bits and pieces more obvious while the original formulations obfuscated them. In the same way some NP-complete problems look harder to me because they seem to require global information while vertex three coloring looks to me like it should be solvable with quite localized information. Another good analogy is probably the way switching between position and momentum eigenstates in quantum physics makes different problems easier to express and handle.
maweki 9y ago
I could be convinced that P=NP, but that would also mean that Co-NP=P and I just couldn't wrap my mind around that one. Co-NP just seems so much harder than NP.
- likelynew 9y ago
  I believe it's opposite i.e. if P=Co-NP, then P=NP.
  - yorwba 9y ago
    Because P=Co-P, that's the same thing.
  - deleted 9y ago
    [deleted]
  - maweki 9y ago
    This is all contained in the collapse of the hierarchy, no matter which way you look at it. It will all be the same.
    - likelynew 9y ago
      So, P=NP implies P=Co-NP?
      - maweki 9y ago
        Yes. Since we already know that P=Co-P, if P were to be shown equal to NP then P=NP=Co-NP=Co-P. All these classes would turn out to be the same since P is closed under complement. Then NP would be as well and everything is equal. That's why this result sometimes is called the collapse if the complexity hierarchy.

by crb002 9y ago

jmcgough 9y ago

P!=NP seems to be the general sentiment, though we're still waiting on the proof :)

tachyonbeam 9y ago
I share the same sentiment, but I think it could be that P!=NP is an unprovable statement. Could be that there's something fundamental about the nature of computing which makes it impossible to prove or disprove it.
- sacheendra 9y ago
  Maybe that could be a thing to prove. Is it possible to prove that something is not provable?
  - jlebar 9y ago
    See http://www.scottaaronson.com/papers/indep.ps http://www.scottaaronson.com/papers/indep.ps
  - emmab 9y ago
    > Is it possible to prove that something is not provable? It's possible to prove that something is not provable within some axiom set. See: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent...
  - infogulch 9y ago
    In general yes. [1] I don't know about PvNP [1]: https://math.stackexchange.com/questions/2027182/how-do-we-prove-that-something-is-unprovable https://math.stackexchange.com/questions/2027182/how-do-we-p...
  - auggierose 9y ago
    Yep. That's what Gödel did.
- emmab 9y ago
  Something is only unprovable wrt an axiom set. You can add new axioms to an existing axiom set that can be semi-decidably proved inconsistent given the rest of the axiom set. https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... For a theory of how to choose an axiom set probabilistically, see: https://intelligence.org/2016/09/12/new-paper-logical-induction/ https://intelligence.org/2016/09/12/new-paper-logical-induct...
  - Houshalter 9y ago
    You can't just add arbitrary axioms. It's entirely possible to have a statement that's unprovable with any axioms mathematicians would consider reasonable.
    - emmab 9y ago
      An axiom can be wrong wrt the standard model for some first-order theory: http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers/ http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers... But, demonstrating an axiom is inconsistent with the standard model of peano arithmetic or ZFC is in the general case uncomputable. For example, an axiom that claims some program halts when it does not actually halt cannot in general be proved to be inconsistent wrt the standard model, because otherwise one could decide the halting problem.
- sjg007 9y ago
  What if it is not computable?
- DonbunEf7 9y ago
  I used to think this, too, but Aaronson changed my mind with the observation in [0] that, if P != NP is independent, then it would necessarily imply a lot of what we would demand from a constructive P = NP proof. In particular, we could get some pretty hilarious improvements on those exponents in NP-complete algorithms, to the point where they become tractable for day-to-day computing. There is a sense in which any complexity class which is self-low is "physical", or analogous to machines which we might build by hand with modular designs. A self-low class doesn't gain any additional power when relativized with itself as an oracle, and this directly corresponds to building a physical machine out of smaller machine modules. We know that P is self-low. It seems that the universe insists that either we are able to build machines which tractably solve NP-complete problems, or not, but there is no in-between position. [0] http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf p28
- tgflynn 9y ago
  I don't see how it could be unprovable. As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity. You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n. Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n. This is now a question about a finite set which has a definite answer which could, in principle, be determined by enumerating all possible algorithms (represented, for example, by boolean circuits with some large size bound) for a particular NP complete problem for problem sizes up to n. Of course this would probably take many times the lifetime of the universe to actually do, but it could be done in principle. So the question of how the minimum circuit size which solves an NP complete problem scales with n has a definite answer.
  - contravariant 9y ago
    >enumerating all possible algorithms [...] for problem sizes up to n. Please keep in mind that this includes an algorithm that has precomputed all possible solutions and retrieves their value from a list. In fact I find it hard to say for certain that you can't for instance assume the existence of an algorithm that calculates the answers to some NP problem in constant time, but which takes an amount of time that can't be proven to be smaller than any other number. This would lead to a situation where P != NP may not be provable.
  - ColinWright 9y ago
    > I don't see how it could be unprovable. It's quite plausible that it's unprovable, although you would have to be specific about the axiom system you're using. > As far as I know the only way a theorem can be unprovable is if it makes statements involving infinity. It does. > You can reduce P vs NP to a question involving only finite sets by choosing some finite n, which can be arbitrarily large. It should be large enough so that the asymptotic behavior of any algorithm would dominate at n. No, you can't. You don't know how large that n has to be, so you have to prove it for arbitrarily large n, and that's the "infinity" that you're dismissing. > Instead of asking about the scaling behavior of an algorithm as n approaches infinity you now ask about its scaling up to the finite value n. So you've changed the question to one that can be proven. The original question might still be unprovable. So I don't see how your comment really makes any sense at all. Perhaps you could be a little more precise.
- CJefferson 9y ago
  I don't think it's impossible to prove, I think we just aren't yet good at proving it. One reason I believe P!=NP is I can imagine what a proof of P=NP would look like -- just write a C program that solves SAT or Sudoku or something, in polynomial time, and prove it's correctness and execution time. There are tens of thousands of papers which do that, for various problems. I can't really imagine what a proof of P!=NP would look like, proving something doesn't exist is extremely hard, particularly because for any particular instance of an NP problem, there is a problem which solves it "by luck".
  - chx 9y ago
    Even if it'll be a constructive proof, it doesn't mean you could actually write the C program. It'll be like, here are the steps to construct an algorithm for this NP complete problem and then the number of steps itself is bound by n^(absurdly large number) and then prove the complexity is bound by n^(another absurdly large number). It will have zero practical consequences.
- rlanday 9y ago
  There are many, many things that are most likely provable that have not been proven yet. Fermat's Last Theorem went 358 years before it was finally proven. Theoretical computer science is a very young field by comparison.
  - Houshalter 9y ago
    Years is a bad measure to use. The number of mathematicians has grown exponentially over the last 400 years. Both because of population growth and the Flynn effect, and because our society is a lot richer and we spend more on mathematical research.
    - rlanday 9y ago
      On the other hand, can nine women have a baby in a month?
mixedmath 9y ago
I think it's interesting that Knuth came to believe that P=NP. See question 17 and its response in this interview with him [1]. [1]: http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858

padobson 9y ago

Yeah, proving it is not going to be much of a game changer. Most everyone already assumes it's true. But if someone were to prove the opposite, the entire technology world would shift dramatically, so it will certainly help to have a proof for this.

Guvante 9y ago
That is assuming the constant end up being in the realm of reasonable. `O(2^N)` and `O(N^1000)` are no different for any useful values of `N`.
rickduggan 9y ago
Wouldn't someone proving it true be a game changer in that it would preclude the ability of anyone to prove the opposite?

danbruc 9y ago

I have been convinced that P==NP since my first exposure to the topic in university. There are NP complete problems where I can really not imagine how they could be solved quickly, but vertex three coloring just looks so doable to me by some informal intuitive arguments. In another life I would devote my life to fleshing out the argument and proving P==NP. Or at least learn where my intuitive argument fails.

artosispylon 9y ago
By definition, each NP-complete problem is provably as hard as another though. Graph coloring can be reduced in polynomial time to every NP-C problem. It doesn't really make sense to me that one problem can just "look so doable" when they're really just the same problems.
- danbruc 9y ago
  They are of course all reducible to each other but that doesn't necessarily mean that they are all equally hard to attack. That's very common in mathematics where reformulating the problem can make the relevant bits and pieces more obvious while the original formulations obfuscated them. In the same way some NP-complete problems look harder to me because they seem to require global information while vertex three coloring looks to me like it should be solvable with quite localized information. Another good analogy is probably the way switching between position and momentum eigenstates in quantum physics makes different problems easier to express and handle.

maweki 9y ago

I could be convinced that P=NP, but that would also mean that Co-NP=P and I just couldn't wrap my mind around that one. Co-NP just seems so much harder than NP.

likelynew 9y ago
I believe it's opposite i.e. if P=Co-NP, then P=NP.
- yorwba 9y ago
  Because P=Co-P, that's the same thing.
- deleted 9y ago
  [deleted]
- maweki 9y ago
  This is all contained in the collapse of the hierarchy, no matter which way you look at it. It will all be the same.
  - likelynew 9y ago
    So, P=NP implies P=Co-NP?
    - maweki 9y ago
      Yes. Since we already know that P=Co-P, if P were to be shown equal to NP then P=NP=Co-NP=Co-P. All these classes would turn out to be the same since P is closed under complement. Then NP would be as well and everything is equal. That's why this result sometimes is called the collapse if the complexity hierarchy.