vznuri@... wrote:
>
> hi TM, thanks for the fantastic post re: 2-cnf/tarjan.
> lots of deep/important ideas that I must admit I am not
> conversant with. it sounds to me like the component
> ideas of tarjan are probably also related to AP/MNs
> work on coming up with an underlying structure of
> graphs. (maybe they can tell us how, if so).
>
> I am sure as you say the 2-cnf ideas have relevance to 3-cnf.
> in fact I am always wondering what the most efficient algorithm
> for SAT is, and it seems totally plausible to me it would be
> an elegant generalization of a known polynomial time algorithm
> for the subcases such as 2-cnf.

<...>

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

Edgers,

Perhaps a few of you will be interested in a slightly
different way of looking at PropSat problems, by way
of C.S. Peirce's "Alpha" Subsystem of Logical Graphs,
some extensions of which I have developed over the
past 30 years or so.

Although I see nothing virtual-earth-shaking coming out
of this calculus any time soon, as far as the hard part
of NP-completeness goes, since the worse-case instances
still remain at O(2^k) in complexity, both space & time,
this formal language does make possible a comparatively
efficient algorithm for outlining all of the satisfying
interpretations (logical value assignments) of "typical"
propositional expressions, expressing them in the style
of a canonical form that is roughly analogous to a DNF.

I can explain this language, and the algorithms that
I have implemented for managing it, later in full if
anybody is interested, but the quickest and the most
painless way for me to introduce it at the moment is
to give you the links to presentations in other fora,
in particular, the "Conceptual Graphs" (CG) list and
the "Standard Upper Ontology" (SUO) discussion group:

http://www.virtual-earth.de/CG/cg-list/msg03351.html
http://www.virtual-earth.de/CG/cg-list/msg03352.html
http://www.virtual-earth.de/CG/cg-list/msg03353.html
http://www.virtual-earth.de/CG/cg-list/msg03354.html
http://www.virtual-earth.de/CG/cg-list/msg03376.html
http://www.virtual-earth.de/CG/cg-list/msg03379.html
http://www.virtual-earth.de/CG/cg-list/msg03381.html

http://ltsc.ieee.org/logs/suo/msg01406.html
http://ltsc.ieee.org/logs/suo/msg01546.html
http://ltsc.ieee.org/logs/suo/msg01561.html
http://ltsc.ieee.org/logs/suo/msg01670.html
http://ltsc.ieee.org/logs/suo/msg01966.html
http://ltsc.ieee.org/logs/suo/msg01985.html
http://ltsc.ieee.org/logs/suo/msg01988.html

http://grouper.ieee.org/groups/ltsc/logs/ontology/msg00072.html

E-joy!

Jon Awbrey

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤