6
$\begingroup$

I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable.

Does it make sense to discuss the complexity of computing a function that cannot be computed?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
22
$\begingroup$

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a problem that is not computable in the model of computation you're talking about. Or, to put it the other way around, it only makes sense to talk about the computational complexity of the halting problem with respect to models of computation in which that problem is computable. For example, you could talk about the complexity of recursively enumerable problems using Turing machines with an oracle for the halting problem as your model of computation.

The proof you link to does not show that the halting problem is in NP. It shows that the halting problem is NP-hard, which just means that every problem in NP is polynomial-time reducible to the halting problem.

Improve this answer
$\endgroup$
12
$\begingroup$

The halting problem is not in NP. It is, however, NP-hard, which is not the same thing.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Apologies, that was clumsy of me. However, NP-Hard is still a description of the problem's complexity, so the question remains valid. $\endgroup$
    – M Smith
    Commented Mar 9, 2018 at 19:03
  • 14
    $\begingroup$ @MSmith Quite surprisingly, NP-hardness is not "a description of the problem's complexity" from a purely formal point of view. A being NP-hard implies that, if A can be decided under a certain time, then every NP problem can also be decided in that time plus a polynomial. It does not imply that A can be decided, nor that it "has a complexity" (informally speaking). In practice, however, NP-hardness is commonly studied for problems which are known to be decidable, so the confusion is completely understandable. $\endgroup$
    – chi
    Commented Mar 9, 2018 at 19:20
  • 3
    $\begingroup$ True, but that doesn't answer the question of "Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?" $\endgroup$
    – Pharap
    Commented Mar 10, 2018 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.