Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: transitive closure again
Message-ID: <902@cresswell.quintus.UUCP>
Date: 26 Apr 88 00:33:40 GMT
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 41
Keywords: NP-hard

A couple of days ago I bought a copy of
	Computational Complexity and Natural Language
	Barton, G.E, Berwick, R.C, & Ristad, E.S.
	MIT Press, 1987
	ISBN 0-262-02266-4
	US Price: $US 24.95 + tax
It's a fascinating book.  By an odd coincidence, I was rereading the
Takeuchi & Furukawa paper about partial execution, and it has BUP as
an example.  Of central importance in that bottom-up parser is a
predicate can_start(NT, NT1) which is true if there is a derivation
NT -*-> NT1 ..., and this is the transitive closure of the relation
starts_with(NT, NT1) which is true if there is a rule NT -> NT1 ...
Now, in general these non-terminals will be compound terms, and I
found myself wondering if there was an easy proof that solving for
can_start/2 was hard.

In retrospect, it was glaringly obvious, and I'm kicking myself for
not spotting it sooner.  Suppose you have a base table
	base(From, To).
and are interested in
	closure(From, To) <-> base(From, To)
	    | closure(From, Mid) & closure(Mid, To).

We already knew that if the base/2 table is ground, the closure can be
computed in (hand-wave) cubic time, and that if the base/2 table can
contain arbitrary terms, the closure may not be finite.  What about
in-between versions?  The simplest interesting generalisation I could
think of is where all the clauses in base/2 have the form
	base(f(X1,...,Xn), g(Y1,...,Ym))
where the Xi and Yj are either constants or variables.

It turns out that finding the closure of such a base table is NP-hard.
[You can embed SAT in closure; you get one base/2 clause for each
literal.]

The bottom line is that it doesn't matter how much magic we put into
our logic programming languages, NP-hard is NP-hard, and we're not going
to get cheap transitive closures.

Are there any interesting versions of the transitive closure problem
in P other than the ground case?  [Maybe if base/2 satisfies an FD?]