FOM: Request for help with complexity problem

[Neil Tennant]

Would any fom-er who knows the computational complexity of the
following decision problem please let me know what it is, and where one
can find the proof?

The problem is stated in the style of Garey and Johnson, and its
statement is preceded by a few definitions.
______________________________________________________________________

Let S be any set of 'sentences'. 

Definitions:

An implication relation on S is a set of ordered pairs (A,s) where A
is a subset of S and s is in S.

If R is an implication relation then R is clean just in case:

   if (A,s) is in R and (B,s) is in R and A is a subset of B then A=B.

For any subset X of S, define [X]_R, the 'R-closure of X within S' as
follows:

  Y_0 =df X

  Y_(n+1) =df Y_n U {s in S | for some subset A of Y_n, (A,s) is in R}

  [X]_R =df U_j Y_j

______________________________________________________________________

The decision problem is as follows.

INSTANCE:

A finite set S of 'sentences';
a subset I of S consisting of 'initial sentences';
a sentence t in S;
a clean implication relation R on S;
a positive integer K <= |I|.

QUESTION:

Is there a subset J of I with |J| <= K such that t is in [J]_R ?


___________________________________________________________________
Neil W. Tennant
Professor of Philosophy and Adjunct Professor of Cognitive Science
230 North Oval
The Ohio State University