# FOM: Re: Request for help with complexity problem

Neil Tennant neilt at mercutio.cohums.ohio-state.edu
Sun Dec 16 11:23:28 EST 2001

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

```