For reasonable numberings of Turing machines, the halting problem is NP-hard. For unreasonable numberings, it might not be.
-
-
Replying to @ModelOfTheory
By "reasonable", I mean an admissible numbering that is computable in polynomial time from a practical format for representing programs.
1 reply 1 retweet 1 like
For reasonable numberings, the halting problem is RE-complete (and hence hard for any subclass of RE) under polynomial-time reductions.
0 replies
1 retweet
1 like
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.