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

Uncomputable problems are not necessarily NP-hard. You can for example encode a version of the halting problem such that the instances are simply very long. For example, consider the language L defined by k is in L iff k=2^2^2^n for some n and nth Turing machine halts on the blank tape (some reasonable listing of Turing machines). In order to feed an NP-hard problem to an L-oracle, one needs to ridiculously expand the length of the problem far more than polynomial length so this certainly can't be done in polynomial time.



Ah, good one. Hooray for padding tricks!




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

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

Search: