FOM: Request for help with complexity problem
Neil Tennant
neilt at mercutio.cohums.ohio-state.edu
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'.
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
More information about the FOM
mailing list