4 ms·

Before there was AlphaGo, many top Go players believed that understanding Go is somehow special in helping us to understand the universe. The AlphaGo was a shoc

by js8 3y ago

Before there was AlphaGo, many top Go players believed that understanding Go is somehow special in helping us to understand the universe. The AlphaGo was a shock, because it turned Go into "just another game", which can be beaten by enough calculations on a powerful computer. I think the mathematics is the same. Lot of its beauty we cherish, because we don't properly understand it on the "raw" level of SAT (I would write logic, but I really mean the simplest metalogic you need), which is evidenced by our lack of understanding of P vs NP. Once it is understood, the process of "doing math" will be understood algorithmically, and it will become "boring" or "dull". But as I said, I don't think lack of universal meaning (or lack of mystique) has to detract from the beauty of mathematics.

constantcrying 3y ago
Some facts to consider: - Polynomial problems can still require enormous computing power to the point they are unsolvable. Even if tomorrow there is an algorithm transforming every NP problem to a P problem, not all problems will be feasibly solvable. A O(n^100) Problem is still P. - P vs. NP is about algorithmic complexity, it has no implications about mathematics being an algorithm or not. - The most likely outcome is that P and NP are different, in which case there are zero implications on computational efficiency. - Considering mathematical statements as algorithms has happened for a long time. Any outcome of P vs. NP has limited implications on the philosophy behind it. It just might make it somewhat better. You just don't understand what P vs. NP is about, your posts are bizarre in the actual context of the problem statement. The implications on mathematics just aren't what you think they are.
- js8 3y ago
  I think what's more fundamental than just answering P vs NP, is what exactly makes boolean functions hard to (pseudo)inverse? And it's the latter where answering (unless the answer comes from an oracle) the former will help. And this question is crucial, because everything we can ask computers (or restated, math with real-world applications) can be rephrased in terms of finding a solution to a SAT instance. It can be a very large instance but if there is a practical way of approaching the problem, it shouldn't matter. I think you're assuming that future computer scientists and mathematicians will continue to run (many different) algorithms, and I don't. I think there might be a single algorithm, a SAT solver, which will subsume all others.
  - constantcrying 3y ago
    Do you not realize that SAT might just be O(2^n) at best? Even if by a gigantic miracle SAT is in P, unless there is another incredibly great miracle and it is something like O(n^3), which would almost certainly be the greatest discovery of CS, it would not replace almost any other algorithms? Simply because many of the most important ones are O(n^2) or even less. >I think there might be a single algorithm, a SAT solver, which will subsume all others. This is legitimately insane. You might as well hope for free energy, FTL Travel, or magic.
    - js8 3y ago
      > Do you not realize that SAT might just be O(2^n) at best? Yes, but that's the worst case on all possible instances. Even with this worst case performance, there might be an algorithm that works on par with other algorithms that specialize only on certain instances. E.g. there can be an O(2^n) algorithm for general SAT which performs in O(n^(3/2)) on XORSAT. We simply don't understand the problem well enough to tell. Also the set of worst-case instances can be vanishingly small in practice.
      - constantcrying 3y ago
        The average case is also O(n^2). You have a completely utopian idea about what might be computationally feasible. I don't even know what you are arguing. Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction.
        samatman 3y ago
        > Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction. These are, as I'm sure you know, utterly different. Nuclear fusion is real, 'simple' and 'near free' are engineering problems. If human civilization lasts long enough, and continues to progress technologically, we'll have that, for some value of 'simple' and 'near free'. On the other hand, the conjecture that SAT is algorithmically feasible may be disproven, and in my opinion, will be. That would be "just isn't going to happen".

by js8 3y ago

constantcrying 3y ago

Some facts to consider: - Polynomial problems can still require enormous computing power to the point they are unsolvable. Even if tomorrow there is an algorithm transforming every NP problem to a P problem, not all problems will be feasibly solvable. A O(n^100) Problem is still P. - P vs. NP is about algorithmic complexity, it has no implications about mathematics being an algorithm or not. - The most likely outcome is that P and NP are different, in which case there are zero implications on computational efficiency. - Considering mathematical statements as algorithms has happened for a long time. Any outcome of P vs. NP has limited implications on the philosophy behind it. It just might make it somewhat better. You just don't understand what P vs. NP is about, your posts are bizarre in the actual context of the problem statement. The implications on mathematics just aren't what you think they are.

js8 3y ago
I think what's more fundamental than just answering P vs NP, is what exactly makes boolean functions hard to (pseudo)inverse? And it's the latter where answering (unless the answer comes from an oracle) the former will help. And this question is crucial, because everything we can ask computers (or restated, math with real-world applications) can be rephrased in terms of finding a solution to a SAT instance. It can be a very large instance but if there is a practical way of approaching the problem, it shouldn't matter. I think you're assuming that future computer scientists and mathematicians will continue to run (many different) algorithms, and I don't. I think there might be a single algorithm, a SAT solver, which will subsume all others.
- constantcrying 3y ago
  Do you not realize that SAT might just be O(2^n) at best? Even if by a gigantic miracle SAT is in P, unless there is another incredibly great miracle and it is something like O(n^3), which would almost certainly be the greatest discovery of CS, it would not replace almost any other algorithms? Simply because many of the most important ones are O(n^2) or even less. >I think there might be a single algorithm, a SAT solver, which will subsume all others. This is legitimately insane. You might as well hope for free energy, FTL Travel, or magic.
  - js8 3y ago
    > Do you not realize that SAT might just be O(2^n) at best? Yes, but that's the worst case on all possible instances. Even with this worst case performance, there might be an algorithm that works on par with other algorithms that specialize only on certain instances. E.g. there can be an O(2^n) algorithm for general SAT which performs in O(n^(3/2)) on XORSAT. We simply don't understand the problem well enough to tell. Also the set of worst-case instances can be vanishingly small in practice.
    - constantcrying 3y ago
      The average case is also O(n^2). You have a completely utopian idea about what might be computationally feasible. I don't even know what you are arguing. Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction.
      - samatman 3y ago
        > Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction. These are, as I'm sure you know, utterly different. Nuclear fusion is real, 'simple' and 'near free' are engineering problems. If human civilization lasts long enough, and continues to progress technologically, we'll have that, for some value of 'simple' and 'near free'. On the other hand, the conjecture that SAT is algorithmically feasible may be disproven, and in my opinion, will be. That would be "just isn't going to happen".