6 ms·

P != NP is more likely akin to a fundamental mathematical law, like Noethers theorem [0]. No amount of self improving AI will alter the fundamental laws of phys

P != NP is more likely akin to a fundamental mathematical law, like Noethers theorem [0]. No amount of self improving AI will alter the fundamental laws of physics. More provincially, in our solar system, there's a cap on energy so that any system that uses it will eventually hit a ceiling (like a self improving AI that eats up energy resources at an exponential pace). As motivation for why P != NP, one can think of it as a finite restatement of the Halting Problem [1] in the form of asking whether a (polynomially sized) Turing machine has an input that will halt in K steps. [0] https://en.wikipedia.org/wiki/Noether%27s_theorem https://en.wikipedia.org/wiki/Noether%27s_theorem [1] https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem

js8 3y ago
> As motivation for why P != NP, one can think of it as a finite restatement of the Halting Problem That's a really poor motivation. Analogically, you can think of the NP question as solving a polynomial equation over Z_2. What you're arguing is that because for Z the problem is unsolvable (due to DPRM theorem), then for Z_2, we have to try all the solutions. That argument fundamentally ignores that the source of unsolvability is the infinite nature of Z. For the record, I believe that P=NP (see https://news.ycombinator.com/item?id=35729626 https://news.ycombinator.com/item?id=35729626). I wish people spend more time looking for polynomial algorithm using logic approach, as I am doing (trying to extend the 2SAT and XORSAT proof to 2XSAT). This approach could give new algorithms that actually compose and can be paralelized (DIMACS is a really awkward representation).
- abetusk 3y ago
  Godels incompleteness theorem and the Halting problem are very nearly equivalent. I believe Turing, very soon after hearing about Godels' incompleteness theorem, used it to show the non-existence of the Halting problem. The consequences of Godel's incompleteness theorem and the Halting problem wove into many outstanding problems, including Hilbert's 10th problem. I would argue that computation is a much more natural setting for thinking about these ideas. Whether is recursively enumerable sets, Diophantine equations or set theory doesn't fundamentally matter so much, as they're all equivalent in some way. I wouldn't argue that you, or anyone else, shouldn't think of it in that way, but in my opinion, for many people, myself included, casting it through a computational lens makes more sense. Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. Since Godel's incompleteness, we know that the continuum hypothesis can be true or false depending on which (consistent) axioms you choose, so I would argue that it's not so much which axioms we choose for how we think about infinities that's fundamental but the fact that consistent systems of sufficient complexity must be incomplete. I'm firmly in the P!=NP camp but I commend you for putting your beliefs out there and actually doing the work. I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. The path from problems being "easy" (polynomial) to "hard" (exponential) is not very well understood and even if a problem is, in general, NP-Complete doesn't mean that a particular ensemble of problems being drawn from couldn't be solved by some clever polynomial time algorithm. And of course, P ?= NP still remains an open problem so we still don't understand something pretty fundamental.
  - js8 3y ago
    > Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. > but the fact that consistent systems of sufficient complexity must be incomplete The problem is that if P!=NP, then it would seem to imply (from what I have seen) that there is a large class of finite deduction systems which are incomplete, no matter what rules of inference you pick. This to me is a lot more counterintuitive than simply accepting that finite and infinite are just very, very different worlds, and our intuition easily fails when we transfer results from one to another. And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. > I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. I very much agree. I was originally agnostic on whether P=NP (now I am tilted to believe that P=NP and there is actually an efficient algorithm). I always felt that assuming P=NP ("assuming" in the philosophical not mathematical sense) and looking for a polynomial algorithm (what would the polynomial algorithm have to look like, for example, it would have to represent exponential number of solutions to look at them at once) is a better way to progress on the question rather than assuming P!=NP. (Kinda like if we assume that the world is knowable, we are more motivated to know it, rather than if we assume it's unknowable.) It's also better in practice because if you actually try to construct a polynomial algorithm, and it fails, you will get a much more concrete idea what the obstacle is (a specific set of instances where it fails). I think because of the natural proofs, if you assume P!=NP, then you believe that progressing this way is essentially impossible. So I think that's the reason why people give up, because if you believe P!=NP, resolving it this way is hopeless, and at the same time, nobody has any better idea. However, if you ever so slightly believe that P=NP, and humans are just not smart enough to figure it out in 50 years (remember, it took several centuries to figure out Gaussian elimination, which seems completely obvious in retrospect), then you're not constrained with natural proof limitations and there is no reason for hopelessness.

js8 3y ago

> As motivation for why P != NP, one can think of it as a finite restatement of the Halting Problem That's a really poor motivation. Analogically, you can think of the NP question as solving a polynomial equation over Z_2. What you're arguing is that because for Z the problem is unsolvable (due to DPRM theorem), then for Z_2, we have to try all the solutions. That argument fundamentally ignores that the source of unsolvability is the infinite nature of Z. For the record, I believe that P=NP (see https://news.ycombinator.com/item?id=35729626 https://news.ycombinator.com/item?id=35729626). I wish people spend more time looking for polynomial algorithm using logic approach, as I am doing (trying to extend the 2SAT and XORSAT proof to 2XSAT). This approach could give new algorithms that actually compose and can be paralelized (DIMACS is a really awkward representation).

abetusk 3y ago
Godels incompleteness theorem and the Halting problem are very nearly equivalent. I believe Turing, very soon after hearing about Godels' incompleteness theorem, used it to show the non-existence of the Halting problem. The consequences of Godel's incompleteness theorem and the Halting problem wove into many outstanding problems, including Hilbert's 10th problem. I would argue that computation is a much more natural setting for thinking about these ideas. Whether is recursively enumerable sets, Diophantine equations or set theory doesn't fundamentally matter so much, as they're all equivalent in some way. I wouldn't argue that you, or anyone else, shouldn't think of it in that way, but in my opinion, for many people, myself included, casting it through a computational lens makes more sense. Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. Since Godel's incompleteness, we know that the continuum hypothesis can be true or false depending on which (consistent) axioms you choose, so I would argue that it's not so much which axioms we choose for how we think about infinities that's fundamental but the fact that consistent systems of sufficient complexity must be incomplete. I'm firmly in the P!=NP camp but I commend you for putting your beliefs out there and actually doing the work. I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. The path from problems being "easy" (polynomial) to "hard" (exponential) is not very well understood and even if a problem is, in general, NP-Complete doesn't mean that a particular ensemble of problems being drawn from couldn't be solved by some clever polynomial time algorithm. And of course, P ?= NP still remains an open problem so we still don't understand something pretty fundamental.
- js8 3y ago
  > Not to harp on a small point but I would argue the diagonalization proof of the Halting problem relies on there being different orders of infinity, not that Z itself is infinite. I am philosophically very close to finitism, and I think from the perspective of the Skolem's paradox it's not clear whether different infinities are not just a "mirage", so to speak. The distinction between finite and infinite seems to be much more "real" to me. > but the fact that consistent systems of sufficient complexity must be incomplete The problem is that if P!=NP, then it would seem to imply (from what I have seen) that there is a large class of finite deduction systems which are incomplete, no matter what rules of inference you pick. This to me is a lot more counterintuitive than simply accepting that finite and infinite are just very, very different worlds, and our intuition easily fails when we transfer results from one to another. And as I describe in that other thread, with the 2XSAT being NP-complete, the idea that you have two finite sets in Z_2^n that are each relatively easy to describe (instance of 2SAT and instance of XORSAT), but their intersection (which is in 2XSAT) is somehow "difficult" to describe is just.. really really hard to take seriously. Of course it's just another intuition, but I don't see how anybody who believes that P!=NP can look at this and not start doubting it. > I do believe people throw up their hands when they hear "NP-Complete" when they absolutely shouldn't. I very much agree. I was originally agnostic on whether P=NP (now I am tilted to believe that P=NP and there is actually an efficient algorithm). I always felt that assuming P=NP ("assuming" in the philosophical not mathematical sense) and looking for a polynomial algorithm (what would the polynomial algorithm have to look like, for example, it would have to represent exponential number of solutions to look at them at once) is a better way to progress on the question rather than assuming P!=NP. (Kinda like if we assume that the world is knowable, we are more motivated to know it, rather than if we assume it's unknowable.) It's also better in practice because if you actually try to construct a polynomial algorithm, and it fails, you will get a much more concrete idea what the obstacle is (a specific set of instances where it fails). I think because of the natural proofs, if you assume P!=NP, then you believe that progressing this way is essentially impossible. So I think that's the reason why people give up, because if you believe P!=NP, resolving it this way is hopeless, and at the same time, nobody has any better idea. However, if you ever so slightly believe that P=NP, and humans are just not smart enough to figure it out in 50 years (remember, it took several centuries to figure out Gaussian elimination, which seems completely obvious in retrospect), then you're not constrained with natural proof limitations and there is no reason for hopelessness.