Re: Propositions

Message-id: <>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 24 Feb 1994 16:45:14 -0800
To:, 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                           
USC/ISI, 4676 Admiralty Way, Marina del Rey, CA 90292      (310) 822-1511