[Haskell-cafe] 2-CNF Sat algorithm/haskell code
Ron de Bruijn
rondebruijn at yahoo.com
Tue Mar 16 12:19:55 EST 2004
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
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