Dear all, a big challenge for #SAT programs is counting Dedekind numbers (number of monotone n-variable Boolean functions). Every property of n-variable...
805
Martyn Amos
M.Amos@...
Jul 1, 1999 12:11 pm
Preliminary Announcement: 16th British Colloquium for Theoretical Computer Science BCTCS 16, April 10-12 2000, Liverpool, UK The 16th annual British Colloquium...
806
d p
danpeh@...
Jul 1, 1999 8:28 pm
Thanks much Mati! Do you know of any follow-up or remotely related work? In this message, I post the Dimacs form for the first few dedekind numbers. In the...
807
d p
danpeh@...
Jul 1, 1999 8:54 pm
Here's a translation of the aforementioned 2-cnfs. That is, given a boolean expression P, give the expression for Q that encodes all the satisfying ...
808
d p
danpeh@...
Jul 2, 1999 12:08 am
Well, D(7) took 48 minutes. Not as fast as Mati's 27 minutes, but not too shabby! Note again, that components do help alot on these counting instances, but by...
809
busygin@...
Jul 2, 1999 7:28 am
Hi All, ... That is the point! Indeed, there are a lot of PSpace-complete games of *two* players where universal quanifier arises from arbitrariness of...
810
kvanette@...
Jul 2, 1999 2:23 pm
I don't know if this topic has come up previously, but the Average-Case Complexity Forum (URL: http://www.uncg.edu/mat/avg.html ) might be of some interest to...
811
Vladimir Z. Nuri
vznuri@...
Jul 2, 1999 7:37 pm
Dan, a few points: if you want to do something, consider doing it yourself.. this is what I was hinting at. you seem to have a bit of free time lately!! to the...
812
d p
danpeh@...
Jul 2, 1999 9:28 pm
... That's Yuri Gurevich and friend's work! It's pretty interesting, and gives some good understanding about what happens when one class is polynomially ...
813
d p
danpeh@...
Jul 2, 1999 10:09 pm
... I have, haven't I? Maybe I think NP =? PSpace is the right question to be investigating. That is, if you want progress to be made! And as for...
814
Stas Busygin
busygin@...
Jul 3, 1999 2:08 pm
... I noticed all Q clauses for Dedekind numbers are in form of (~xi OR ~xj), i.e. they always express pairwise contraditions among variables. Dan, is it so...
815
d p
danpeh@...
Jul 3, 1999 6:13 pm
... The Q expressions in simple form are all "monotone". That is, all literals appear only positively, or all appear only negatively. Whether the literals are...
816
Anatoly D. Plotnikov
aplot@...
Jul 4, 1999 12:48 pm
Hello everybody, Recently, the discussion was between Vladimir and Dan regarding changing this charter. I would like to expound my point of view. I believe...
817
d p
danpeh@...
Jul 4, 1999 8:24 pm
... I agree, and I'm happy for the forum, but a little disappointed in the (un)responsiveness of the list members. My problem. As far as changing the charter,...
818
Claude Chaunier
claude@...
Jul 4, 1999 9:23 pm
Hi Dan and all, I was away for 6 months, mostly playing with Slovak and linguistic. Wow, what a reading for my last night -- 500 theory-edgy messages since...
819
Klaus D. Witzel
kWitzel@...
Jul 5, 1999 10:08 am
As some of you may have noticed from my silence, I was "out of cyberspace" for a couple of weeks. wrt of counting satisfying assignments, I was thinking about...
820
Anatoly D. Plotnikov
aplot@...
Jul 5, 1999 3:28 pm
Hello everybody, There are a few persons on this list, who investigates SAT. I would like to understand, what is a worse case for SAT? It is known, classlcaly,...
821
d p
danpeh@...
Jul 5, 1999 6:13 pm
... Hi Claude! Welcome back! Thanks for the info about D(8). ... You understand pretty well. The "initial" expression for P is created using Mati's...
822
Vladimir Z. Nuri
vznuri@...
Jul 5, 1999 9:50 pm
hi everyone, a few odds & ends comments on the recent posts by respected "members". I've been away for a few days over the 4th of july weekend (independence...
823
Vladimir Z. Nuri
vznuri@...
Jul 5, 1999 10:10 pm
I do not really want to start a discussion on the charter on the list-- its one of the few givens that we have to start out with on the list. I am happy to...
824
Vladimir Z. Nuri
vznuri@...
Jul 5, 1999 10:12 pm
there are not many rules here, but let me give everyone else here a few guidelines that will help.. I will add these to the FAQ at some point. 1. respect my...
825
Vladimir Z. Nuri
vznuri@...
Jul 5, 1999 10:22 pm
dan, there are are SEVERAL DISTINCT ISSUES you are constantly mixing up in your posts on this subject. (1) is NP=?Pspace an interesting problem D--, almost...
826
d p
danpeh@...
Jul 5, 1999 11:49 pm
Hi Klaus! Thanks for the substantive example. If anyone has others they'd like to see worked on a little bit, please send them! Fodder for a decent paper...
827
busygin@...
Jul 6, 1999 7:00 am
Hi All, ... (snip) ... Sorry, I don't understand your claim on polynomiality. For the sake of simplicity, let N=n. Then your coding of SAT gives size=2*n^2 for...
828
Vladimir Z. Nuri
vznuri@...
Jul 6, 1999 7:52 pm
maintained by joseph culberson http://web.cs.ualberta.ca/~joe/Coloring/index.html although it has been mentioned here before, the SATLIB page is looking very...
829
d p
danpeh@...
Jul 6, 1999 8:01 pm
... I'm looking for small examples to analyze the behavior and structure of Q. To repeat the definition: for a given boolean expression P, build an...
830
d p
danpeh@...
Jul 6, 1999 8:03 pm
The first message didn't get thru. Apologies if you see this twice! ... I'm looking for small examples to analyze the behavior and structure of Q. To repeat...
831
adall@...
Jul 6, 1999 9:15 pm
Hi all, I'm looking for some good books on complexity analysis - the sort you would use to help you do a proof (or counter one) of polynomial bounding of some...
832
Vladimir Z. Nuri
vznuri@...
Jul 6, 1999 10:12 pm
I mentioned that I think a reasonable topic here related to some of Dan's ideas on the difficulty of pursuing the mathematical life is a historical study of...
833
Sommer Gentry
gentry6@...
Jul 6, 1999 10:28 pm
Actually, I believe that Alan Turing's troubles in life were related to his mathematical genius only in that it had brought him notoriety and an important...
