Minimum Axiom Set

We’re back!  After a crazy spring and summer, I’m going to try to get back on track posting the rest of these problems.  We only have a couple of sections left.

I hope things have been going well for anyone reading this, and that you have been staying safe.

I’ll admit that one of the reasons I’ve been putting off restarting is because I had a very hard time understanding this next problem and the paper talking about it.  But taking some time off might have helped because I think I have come up with an alternate reduction. Here’s my attempt at it.

The problem: Minimum Axion Set.  This is problem LO17 in the appendix.

The description: (I’m going to use a different definition than G&J’s, but one I think is equivalent, because thinking of this problem in terms of propositional logic and languages like Prolog helped me a lot.)

Suppose we have a set of sentences S, some subset T of which are true  Suppose we have a set of “implications” R of the form:

A->s

..where A is some subset of A (the terms of which are joined by AND clauses), and s is a sentence in S. We can say that s is derivable from A.

We’re also given an integer K.

Can we create a set S0 of S, of size K or less, where everything in T is either in S0 or derivable (possibly in multiple steps) from S0?

Example: Let S = {p,q,r,s,f} and T = {p,q,r,s}.

Let our set of implications be:

p->r

r∧q -> s

..Then the set {p,q} would be an axiom set of size 2.  We could use the first implication rule to derive r, and then once we have r, we can use the second implication rule to derive s.  Notice that since f was in S, but not in T, we don’t have to find a way to derive it.

(If you’re reading along with the G&J book at home, each of these “rounds” of new derivations is one of the Si sets of true sentences.  We get a new Si set by taking the old Si-1 set and adding anything new that was derived by sets of elements in Si-1)

Reduction: G&J say to use X3C, but they refer to a paper by Pudlak which seems to use Vertex Cover.

..but this is where I stop being able to follow things.  Part of this is that the paper is from the earlier days of NP-Completeness (1975) and so uses a format and a language that’s not standard now, part of it is that because the paper was written in 1975, there are a lot of hand-written symbols on the paper that are hard to decipher.  Part of the problem too is that Pudlak assumes a level of mathematical comfort that I personally have not reached, so it’s hard to follow his constructions.

But, since G&J decided to use X3C, let’s see if we can come up with an X3C reduction.

So we’re given an instance of X3C, which is a set X of 3q elements.  Each element x ∈ X will correspond to a sentence x in T (and S).  We will also have one element in S (but not T) for each collection in C.

Each element of the collection of 3 elements C (a,b,c) will create the following implications:

(a,b,c) -> a

(a,b,c)->b

(a,b,c)->c

We set K = q.  This means that even though we’re theoretically allowed to pick singleton elements from X as our axioms, the only way we will cover all of X (and T) will be to pick the collection elements, which derives 3 elements in T by the implication rules.

If X has a cover, we can choose the elements of the collection as our axioms and derive all elements of T.

If S has a minimum axiom set, the axiom must all be triples, and those q triples must cover all 3q elements of X, which gives us a cover.

Example of my reduction:

Let X = {1,2,3,4,5,6} and C = {(1,2,4), (1,2,6), (2,4,6), (3,4,5), (4,5,6)}

My S set wll be {1,2,3,4,5,6, (1,2,4), (1,2,6), (2,4,6), (3,4,5), (4,5,6)}

My T set will be {1,2,3,4,5,6}

My implications will be:

  • (1,2,4)->1
  • (1,2,4)->2
  • (1,2,4)->4
  • (1,2,6)->1
  • (1,2,6)->2
  • (1,2,6)->6
  • (2,4,6)->2
  • (2,4,6)->4
  • (2,4,6)->6
  • (3,4,5)->3
  • (3,4,5)->4
  • (3,4,5)->5
  • (4,5,6)->4
  • (4,5,6)->5
  • (4,5,6)->6

We need to find a set of 2 elements of S that will eventually derive all of T.

A solution to the X3C instance would be {(1,2,6), (3,4,5)}.  This covers all of X, but also in the implications rules will also derive all of T.

Difficulty: I feel like thinking about this in my terms is much easier than either G&J’s, or Pudlak’s.  It’s so much easier that I’m worried about losing something in the translation.  So I’d give this a 6 if I’m right, but trying to follow the actual definitions and proofs is at least a 9.

Leave a Reply

Your email address will not be published. Required fields are marked *