I'm studying Comparability and Complexity, and through the course, a number of problems (namely, the halting problem for Turing Machines, etc.) have been proven undecidable through elementary proofs and reductions.

Next, the course discusses polynomial time reductions between several problems, which makes sense: it's reasonable to explore which problems are "about as hard".

Finally, we discuss such polynomial time reductions between a few undecidable problems. For example, we prove that $HALT_{TM}$ is polynomial-time reducible to $A_{TM}$, but that $ALL_{TM}$ is not polynomial-time reducible to $E_{TM}$.

This threw me off a bit - if two problems are undecidable, why it's interesting to investigate complexity properties of them?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.