4 ms·

It’s a joke, it’s mathematically unsolvable. Though even if it were I don’t see the connection to encryption?

ndsipa_pomu 3y ago
Sorry if I got wooshed. It's currently unsolved, but I don't think that it's been proved to be unsolvable as surely that would prove P ≠ NP. The connection to encryption is that integer factorisation could then be solved in polynomial time which would break current systems, though in theory a much longer key length could be used to try to outpace computer power, especially if the polynomial algorithm is hugely inefficient. Edit: I see that the halting problem has indeed been proved to be unsolvable and it doesn't imply P ≠ NP
- explaininjs 3y ago
  P/NP and Halting are entirely different concepts. I suggest reading up on the Halting problem - it’s actually very mind opening. Edit: it wouldn’t be a stretch to call it the most important result in all of mathematics
  - ndsipa_pomu 3y ago
    If you have a solution to the halting problem, then it would be possible to cast the P/NP problems in terms of a program and knowing whether or not it halts would allow you to determine whether P=NP.
    - explaininjs 3y ago
      That may be, but statements that start “if false …” aren’t very useful.
    - sharkbot 3y ago
      The halting problem has been proven definitively undecidable via proof by contradiction, by Alan Turing. The proof implicitly created the notion of Turing machines, a key model of computation. There is a solution to the halting problem. It’s that it is undecidable.
  - dreamcompiler 3y ago
    Yes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.
    - explaininjs 3y ago
      I had originally written something to that effect, but recanted after I saw Turing claimed “what I shall prove is quite different from the well-known results of Gödel”. I’d need to sit down longer to determine how equivalent they really are.
      - dreamcompiler 3y ago
        Would love to see the reference for this. I expect he might be referring to the idea of executing an embodied algorithm on a machine, while Gödel was talking about pure math.
        explaininjs 3y ago
        Page 27 here: https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2...
- tsimionescu 3y ago
  The halting problem (writing an algorithm which can take any other algorithm and an initial condition and return true/false for whether it halts or not) has nothing to do with P or NP. Even if all algorithms were solvable in O(n), the halting problem would still be unsolvable.

Sorry if I got wooshed. It's currently unsolved, but I don't think that it's been proved to be unsolvable as surely that would prove P ≠ NP. The connection to encryption is that integer factorisation could then be solved in polynomial time which would break current systems, though in theory a much longer key length could be used to try to outpace computer power, especially if the polynomial algorithm is hugely inefficient. Edit: I see that the halting problem has indeed been proved to be unsolvable and it doesn't imply P ≠ NP

explaininjs 3y ago
P/NP and Halting are entirely different concepts. I suggest reading up on the Halting problem - it’s actually very mind opening. Edit: it wouldn’t be a stretch to call it the most important result in all of mathematics
- ndsipa_pomu 3y ago
  If you have a solution to the halting problem, then it would be possible to cast the P/NP problems in terms of a program and knowing whether or not it halts would allow you to determine whether P=NP.
  - explaininjs 3y ago
    That may be, but statements that start “if false …” aren’t very useful.
  - sharkbot 3y ago
    The halting problem has been proven definitively undecidable via proof by contradiction, by Alan Turing. The proof implicitly created the notion of Turing machines, a key model of computation. There is a solution to the halting problem. It’s that it is undecidable.
- dreamcompiler 3y ago
  Yes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.
  - explaininjs 3y ago
    I had originally written something to that effect, but recanted after I saw Turing claimed “what I shall prove is quite different from the well-known results of Gödel”. I’d need to sit down longer to determine how equivalent they really are.
    - dreamcompiler 3y ago
      Would love to see the reference for this. I expect he might be referring to the idea of executing an embodied algorithm on a machine, while Gödel was talking about pure math.
      - explaininjs 3y ago
        Page 27 here: https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2...
tsimionescu 3y ago
The halting problem (writing an algorithm which can take any other algorithm and an initial condition and return true/false for whether it halts or not) has nothing to do with P or NP. Even if all algorithms were solvable in O(n), the halting problem would still be unsolvable.