[Haskell-cafe] 2-CNF Sat algorithm/haskell code

Ron de Bruijn rondebruijn at yahoo.com
Tue Mar 16 12:19:55 EST 2004

Dear Haskellers,

Today I searched over more than an hour on the web to
find an implementation of an algorithm that was first
written in the 1970's that solves 2-Conjuntive Normal
Form logical sentences in polynomial time. 

The only thing I could find were some homework
assignments for students of universities and I learned
that there exist an algoritm for 2-CNF. Although I am
a student, what I am doing is no homework.

I believe the datastructure used was a strongly
connected graph (perhaps this rings any bells). 

If you don't know any implementation in any imperative
language or functional language (not to far off when
compared to Haskell), a clear pseudo-code description,
either written by yourself or a URL to a webpage/paper
with that information would also be very welcome.

Thanks in advance,
    Ron de Bruijn

P.S. This is really offtopic, but I would like to hear
some opinions about this project:

I don't know whether they are for real, but when this
works it would greatly impacts the use of inefficient
functional programs(when applied to it ofcourse). Like
in Haskell,
a lot of programs could be written like:
[x|x<-someList, somePred x]
Although they computationally seen would be very slow,
without "supercompilation", with they would perform
just as good as some smart way of doing it.

Do you Yahoo!?
Yahoo! Mail - More reliable, more storage, less spam

More information about the Haskell-Cafe mailing list