research on systematically attacking multiple instances of undecidable problems

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 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. 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 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. 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 of Beigel, Fortnow, and Pavan, and this book of Hemaspaandra and Torenvliet. The concept of bounded queries in computability and complexity is also related, see this survey by Gasarch.

Solved by user223 (4,584 )
Mar 12, 2015 at 18:19