Are there some undecidable problems for which there are efficient heuristic algorithms, that succeed on a sufficiently large subset of inputs to be worth using?

The one application that comes to mind is program static analysis: clearly undecidable (assuming infinite memory – I believe that it is PSPACE-complete if memory is finite but no practical algorithm I know of makes use of this, other than to bound the values of pointers), but in some cases it is possible to prove that a program satisfies a certain property.

  • $\begingroup$ It sounds like you've answered your own question: yes, there are such problems, and you've given one example. What more are you looking for? It sounds like you're calling for a list of examples. We don't have a strict policy for list questions, but there is a general dislike. Also, there's no way anyone can compile a comprehensive list of all such examples, so I'm not seeing how this question is answerable in its current form. $\endgroup$
    – D.W.
    Oct 2, 2016 at 23:48
  • 1
    $\begingroup$ Termination and null pointer checking are two problems that even if undecidable seem to have been subject to lots of attention and heuristics in the literature $\endgroup$
    – ejgallego
    Oct 3, 2016 at 1:33
  • $\begingroup$ @DW I would like to know information about the general class of problems: Why do some undecidable problems have good heuristics, and others do not? $\endgroup$
    – Demi
    Oct 4, 2016 at 2:28


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.