Hacker News Reader

Comment by ndsipa_pomu | Hacker News Reader

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

View on HN

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

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.

That may be, but statements that start “if false …” aren’t very useful.

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.

Yes. The Halting Problem is just Gõdel incompleteness in drag. They're both the same idea and they're both thoroughly proven.

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.

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.

Page 27 here: https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2...

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.

Reply on news.ycombinator.com