FOM: Request for help with complexity problem

Neil Tennant neilt at
Sun Dec 16 08:58:55 EST 2001

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'. 


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

  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.


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|.


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

More information about the FOM mailing list