Re: Propositions

• Mail folder: Interlingua Mail
• Next message: Gerard Ellis: "Re: Propositions"
• Previous message: Harold Boley: "less variables"
• Maybe in reply to: sowa: "Re: Propositions"
• Reply: Gerard Ellis: "Re: Propositions"

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