<p>Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?".<br>
These algorithms (which may be randomized) are sometimes called "errorless heuristics" and have been studied in complexity theory, esp. average-case complexity; see e.g. <a href="http://www.cs.toronto.edu/~thomasw/papers/eha.pdf" rel="nofollow">this paper</a> of Watson and references therein.</p>

<p>A basic question you can ask about a very difficult decision problem is whether it contains <em>any</em> nontrivial easy cases.  E.g. if L is decidable, is there any (deterministic) errorless heuristic A for L that solves $L(x)$ on infinitely many inputs?  This has been explored in the notion of <em>immunity</em> (along with co-immunity, bi-immunity, simplicity and others) in computability theory.  See e.g. <a href="http://en.wikipedia.org/wiki/Simple_set" rel="nofollow">this wiki article</a>.  Complexity-theoretic analogues have been studied as well.</p>

<p>Since you mention multiple instances, I might also interpret the question as looking for research into algorithms which, given instances $x^1, \ldots, x^m$ for a decision problem (i.e. language) L, compute some partial information about the membership/nonmembership of the given strings in $L$.</p>

<p>One of the earliest and most influential works of this type was by Jockusch, who in his dissertation and <a href="http://www.ams.org/journals/tran/1968-131-02/S0002-9947-1968-0220595-7/S0002-9947-1968-0220595-7.pdf" rel="nofollow">this 1968 paper</a> defined "semi-recursive" languages.  L is semi-recursive if there is a computable "selector" function that, given instances $x^1, x^2$, selects one of these two strings as being "logically more likely" to lie in L.  That is, we require that whenever <em>at least one</em> of $x^1, x^2$ lie in L, the string selected by the selector lies in L.</p>

<p>The study of polynomial-time analogues of this concept was initiated by Selman in <a href="http://link.springer.com/chapter/10.1007%2F3-540-09510-1_44" rel="nofollow">this 1979 paper</a>.  Since then there has been tons of work on "p-selective" languages (the polytime version of semi-recursive languages) along with "membership comparable" languages and many other related concepts.  I can't summarize all this work, but consult e.g. <a href="http://people.cs.uchicago.edu/~fortnow/papers/app-sel.pdf" rel="nofollow">this article</a> of Beigel, Fortnow, and Pavan, and <a href="http://www.cs.rochester.edu/u/lane/=semi-feasible/" rel="nofollow">this book</a> of Hemaspaandra and Torenvliet.  The concept of bounded queries in computability and complexity is also related, see <a href="https://www.cs.umd.edu/~gasarch/papers/bdq-survey-tech.pdf" rel="nofollow">this survey</a> by Gasarch.</p>

CC BY-SA 3.0
2015-03-12T18:19:12.803Z
2015-03-12T18:28:24.063Z
2015-03-12T18:28:24.063Z
Andy Drucker
<p>The obvious candidates for these kinds of things are number theoretical. </p>

<ol>
<li><p>The collatz problem springs to mind, see <a href="https://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful">What is the &quot;nearest&quot; problem to the Collatz conjecture that has been successfully resolved?</a>. The cited article is <a href="http://arxiv.org/pdf/0906.3329.pdf" rel="nofollow noreferrer">here</a>, but it is about tag systems rather than number theory.</p></li>
<li><p>Termination is, of course, undecidable, but of course there are some nice algorithms that capture realistic classes of terminating systems. In particular <a href="http://arxiv.org/pdf/1005.0518.pdf" rel="nofollow noreferrer">this paper</a> by Ben Amram gives a neat criterion in which one can decide whether a program is a) polynomial or b) non-terminating, by finding a bound such that, <em>if the program terminates</em>, then it does in less than that bound.</p></li>
<li><p>The problem of finding solutions of integer polynomial equations is, <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow noreferrer">as is well-known</a>, undecidable, but for large classes of problems we <em>do</em> know the solution. See here <a href="https://mathoverflow.net/questions/51987/which-types-of-diophantine-equations-are-solvable">https://mathoverflow.net/questions/51987/which-types-of-diophantine-equations-are-solvable</a>, or <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.378.8001&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">here</a> for instance. The criteria for decidability are generally rather simple in this case and will typically depend on the degree of the equation and some algebraic relation on the coefficients. I don't know whether checking this can be called a "decision procedure".</p></li>
</ol>

CC BY-SA 3.0
2015-03-12T19:58:06.943Z
2015-03-12T19:58:06.943Z
2017-04-13T12:57:54.777Z
cody
<p>this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint.</p>

<p>there are at least some papers of a type that attack multiple instances of undecidable problems. each instance of the general problem is not known <em>a priori</em> to be decidable or undecidable, and the paper describes strategies/techniques for identifying/sorting some into decidable cases, and provides algorithms which decide the problem if it is found to be among the decidable cases.</p>

<blockquote>
  <p>what are papers of this genre, systematically attacking multiple instances of undecidable problems?</p>
</blockquote>

<p>[1] <a href="https://cstheory.stackexchange.com/questions/18846/a-simple-problem-whose-decidability-is-not-known">A simple problem whose decidability is not known</a> / Reyzin, tcs.se</p>

<reference-request><computability><big-list><undecidability>
research on systematically attacking multiple instances of undecidable problems
vzn
# research on systematically attacking multiple instances of undecidable problems

(Asked by: username_0 on 2013-10-11)

this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint.

there are at least some papers of a type that attack multiple instances of undecidable problems. each instance of the general problem is not known *a priori* to be decidable or undecidable, and the paper describes strategies/techniques for identifying/sorting some into decidable cases, and provides algorithms which decide the problem if it is found to be among the decidable cases.

> what are papers of this genre, systematically attacking multiple instances of undecidable problems?

[1] [A simple problem whose decidability is not known](https://cstheory.stackexchange.com/questions/18846/a-simple-problem-whose-decidability-is-not-known) / Reyzin, tcs.se

**Tags:** reference-request, computability, big-list, undecidability

---

## 2 answers

### Answer by username_1 on 2015-03-12. Score: 2 | Accepted answer

Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?".  
These algorithms (which may be randomized) are sometimes called "errorless heuristics" and have been studied in complexity theory, esp. average-case complexity; see e.g. [this paper](http://www.cs.toronto.edu/~thomasw/papers/eha.pdf) of Watson and references therein.

A basic question you can ask about a very difficult decision problem is whether it contains *any* nontrivial easy cases. E.g. if L is decidable, is there any (deterministic) errorless heuristic A for L that solves $L(x)$ on infinitely many inputs? This has been explored in the notion of *immunity* (along with co-immunity, bi-immunity, simplicity and others) in computability theory. See e.g. [this wiki article](http://en.wikipedia.org/wiki/Simple_set). Complexity-theoretic analogues have been studied as well.

Since you mention multiple instances, I might also interpret the question as looking for research into algorithms which, given instances $x^1, \ldots, x^m$ for a decision problem (i.e. language) L, compute some partial information about the membership/nonmembership of the given strings in $L$.

One of the earliest and most influential works of this type was by Jockusch, who in his dissertation and [this 1968 paper](http://www.ams.org/journals/tran/1968-131-02/S0002-9947-1968-0220595-7/S0002-9947-1968-0220595-7.pdf) defined "semi-recursive" languages. L is semi-recursive if there is a computable "selector" function that, given instances $x^1, x^2$, selects one of these two strings as being "logically more likely" to lie in L. That is, we require that whenever *at least one* of $x^1, x^2$ lie in L, the string selected by the selector lies in L.

The study of polynomial-time analogues of this concept was initiated by Selman in [this 1979 paper](http://link.springer.com/chapter/10.1007%2F3-540-09510-1_44). Since then there has been tons of work on "p-selective" languages (the polytime version of semi-recursive languages) along with "membership comparable" languages and many other related concepts. I can't summarize all this work, but consult e.g. [this article](http://people.cs.uchicago.edu/~fortnow/papers/app-sel.pdf) of Beigel, Fortnow, and Pavan, and [this book](http://www.cs.rochester.edu/u/lane/=semi-feasible/) of Hemaspaandra and Torenvliet. The concept of bounded queries in computability and complexity is also related, see [this survey](https://www.cs.umd.edu/~gasarch/papers/bdq-survey-tech.pdf) by Gasarch.


---

### Answer by username_2 on 2015-03-12. Score: 2

The obvious candidates for these kinds of things are number theoretical.

1. The collatz problem springs to mind, see [What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?](https://cstheory.stackexchange.com/questions/11611/what-is-the-nearest-problem-to-the-collatz-conjecture-that-has-been-successful). The cited article is [here](http://arxiv.org/pdf/0906.3329.pdf), but it is about tag systems rather than number theory.
2. Termination is, of course, undecidable, but of course there are some nice algorithms that capture realistic classes of terminating systems. In particular [this paper](http://arxiv.org/pdf/1005.0518.pdf) by Ben Amram gives a neat criterion in which one can decide whether a program is a) polynomial or b) non-terminating, by finding a bound such that, *if the program terminates*, then it does in less than that bound.
3. The problem of finding solutions of integer polynomial equations is, [as is well-known](http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem), undecidable, but for large classes of problems we *do* know the solution. See here <https://mathoverflow.net/questions/51987/which-types-of-diophantine-equations-are-solvable>, or [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.378.8001&rep=rep1&type=pdf) for instance. The criteria for decidability are generally rather simple in this case and will typically depend on the degree of the equation and some algebraic relation on the coefficients. I don't know whether checking this can be called a "decision procedure".


---

