Hacker News new | past | comments | ask | show | jobs | submit login

The problem with this is that proving an algorithm is in P is also undecidable.



How is that a problem with what I said?

You are saying that the decision problem of "Is this algorithm A in P?" is undecidable for arbitrary algorithms A. We don't need a general solution to that decision problem to be able to prove that some particular algorithm is or isn't in P; just like how, we don't need a general solution to the halting problem to prove some particular program does or doesn't halt. The halting problem only means we can't have a computable procedure which will generate such a proof in every case.

The fact that we've actually proven the bounded halting problem is not in P doesn't contradict this. The undecidability of determining whether any arbitrary problem is or isn't in P doesn't prevent us from having a proof that some particular problem is or isn't.

And I said counterpossibly that if the bounded halting problem were in P not EXPTIME-complete, then the halting problem might be practically solvable even if Turing's proof of the undecidability of the unbounded halting problem still held. In this counterpossible, we don't need to be able to solve the decision problem of determining whether an algorithm is in P, all we need is a proof that this one particular algorithm is in P. The undecidability of the decision problem in general tells us nothing about whether we could know its answer for individual cases.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: