Content-Type: text/plain; charset="us-ascii"
Date: Thu, 24 Feb 1994 16:45:14 -0800
To: firstname.lastname@example.org, interlingua@ISI.EDU
Subject: Re: Propositions
>From Len, commenting on Sowa's comments.
>Well, exactly -- the problem then becomes graph-theoretic, and I'm
>not convinced it'll make the proposition-equivalence problem simple.
>It's the "easily computable" part that I don't find at all obvious.
Unless I'm missing something, computing equivalence on Sowa's graphs
is easily reducible to the general problem of (directed) graph isomorphism.
I don't follow concrete complexity results any more, but when I did, no one
had yet found a polynomial time algorithm (and a lot of people had worked
pretty hard trying to find one). Perhaps John means that
its easy to compute graph equivalence in the average case (I would
agree with that).
Robert M. MacGregor email@example.com
USC/ISI, 4676 Admiralty Way, Marina del Rey, CA 90292 (310) 822-1511