FOM: Re: Request for help with complexity problem

[Neil Tennant]

Follow-up question:

Is the problem any less complex if we stipulate that S = [I]_R ?

___________________________________________________________________
Neil W. Tennant
Professor of Philosophy and Adjunct Professor of Cognitive Science
230 North Oval
The Ohio State University
On Sun, 16 Dec 2001, Neil Tennant wrote:

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