ok@quintus.UUCP (Richard A. O'Keefe) (04/26/88)
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?]