# Re: Propositions

macgregor@ISI.EDU
Message-id: <199402250044.AA25850@quark.isi.edu>
X-Sender: macgreg@quark.isi.edu
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 24 Feb 1994 16:45:14 -0800
To: cg@cs.umn.edu, interlingua@ISI.EDU
From: macgregor@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).
- Bob
Robert M. MacGregor macgregor@isi.edu
USC/ISI, 4676 Admiralty Way, Marina del Rey, CA 90292 (310) 822-1511