... this slightly mistaken. correctly, send mail to theory-edge-unsubscribe@... this information is in the header of every outgoing mail message.. or...
1202
Stas Busygin
busygin@...
Jul 1, 2000 10:06 am
Hi Michiro! ... I think no. Surely, the total amount of possible real values for a computer is finite, but this does not mean that we can map them to integers...
1203
Stas Busygin
busygin@...
Jul 1, 2000 11:58 am
Hi Vladimir! I heard about Maslov's research group when I studied at the universtity. They were located in Novosibirsk, Russia, and made some prominent...
1204
Michiro Nasu
nasukun@...
Jul 1, 2000 2:43 pm
Hi Stas! Sorry, at first I must confess that I am quite ignorant around the domain. You wrote, ... This question doesn't relates to any implementation nor...
1205
Stas Busygin
busygin@...
Jul 1, 2000 8:37 pm
... (snip) ... Well, I just don't know is here an appropriate place to explain such basic concepts as eigenpairs but seems it is essential for further...
1206
Stas Busygin
busygin@...
Jul 1, 2000 11:39 pm
To introduce a particular reduction of maximum-weight clique problem to quadratic programming used in QUALEX, consider the graph complementary to the given...
1207
Vladimir Z. Nuri
vznuri@...
Jul 2, 2000 4:36 am
From: "Raghuramaiah Gompa" <gompa@...> Subject: International conference Date: 13 Jun 2000 15:41:30 GMT To: "sci.math.research@..."...
1208
Michiro Nasu
nasukun@...
Jul 2, 2000 8:00 am
Hi Stas! I greatly appreciate your kind help. As I am not only weak in mathematics but also poor in reading and writing English, I ask your pardon for allowing...
1209
Michiro Nasu
nasukun@...
Jul 2, 2000 9:35 am
... Sorry! I missed putting a title to my previous mail. ... Hi Stas! I greatly appreciate your kind help. As I am not only weak in mathematics but also poor...
1210
Michiro Nasu
nasukun@...
Jul 2, 2000 12:43 pm
Hi Stas! It is very probable that your choice hits the mark. You wrote, ... Every NP-complete problem has two faces of positive and negative. For HCP the first...
1211
Stas Busygin
busygin@...
Jul 2, 2000 12:59 pm
... Just several links helpful if somebody needs to recall the basic concepts: Applied Mathematics by Peter J. Olver and Chehrzad Shakiban (a very clear...
1212
Stas Busygin
busygin@...
Jul 2, 2000 1:16 pm
... Hmm, maximum-weight clique problem is not in NP, so to be precious it is NP-hard, not NP-complete. To make them NP-problem we need to introduce a boundary...
1213
Michiro Nasu
nasukun@...
Jul 2, 2000 4:27 pm
Hi Stas! Thanks for your help. I'll go to your school tomorrow. You wrote, ... That is, for negative experiment we need to perform thorough investigation but...
1214
Stas Busygin
busygin@...
Jul 2, 2000 5:57 pm
... (snip) ... Well, Michiro, this will be your first exercise in the school -- the question is "why existence of a ptime exact algorithm for maximum-weight...
1215
Michiro Nasu
nasukun@...
Jul 3, 2000 4:01 am
Stas wrote, ... Very nice formulation! But I wonder whether those arrows have ever such backward arrows as below. NP problem <- SAT01 problem <- reduced SAT01...
1216
Michiro Nasu
nasukun@...
Jul 3, 2000 4:02 am
Stas wrote, ... Very nice formulation! But I wonder whether those arrows have ever such backward arrows as below. NP problem <- SAT01 problem <- reduced SAT01...
1217
Michiro Nasu
nasukun@...
Jul 3, 2000 4:26 am
Hi Stas and all! Stas wrote, ... Farewell Stas! In the famous address of 1900, Hilbert quoted an French mathematician saying "A mathematical theory is not to...
1218
Klaus D. Witzel
kwitzel@...
Jul 3, 2000 3:56 pm
Hi Dan and Michiro, isn't the translation of ¬(expression in CNF) back to CNF form already only possible in exponential time? If you have better than exp,...
1219
Jeffrey Considine
jconsidi@...
Jul 3, 2000 6:05 pm
... If there was a polynomial time algorithm for this, then P=NP. This would give a P-time algorithm for converting from CNF to DNF and satisfiability of DNF...
1220
Klaus D. Witzel
kwitzel@...
Jul 6, 2000 11:12 am
... only ... give ... DNF is ... I understand your argument and think we both mean the same. Let me add a question to "DNF is easy": say we negate a CNF...
1221
Jeffrey Considine
jconsidi@...
Jul 6, 2000 12:23 pm
... The SATISFIABILITY of DNF is easy since each component can be examined separately. Showing that it is unsatisfiable is exactly equivalent to the ...
1222
Stas Busygin
busygin@...
Jul 6, 2000 12:58 pm
Hi Klaus! `Satisfiability' for a boolean expression means `the ability to attain true value'. Surely, the finding of zero for DNF is the same that...
1223
Vladimir Z. Nuri
vznuri@...
Jul 7, 2000 4:55 am
hi everyone. recently a longtime member sent me mail asking for me to moderate recent threads. I appreciate this as a way to handle these situations. if anyone...
1224
Vladimir Z. Nuri
vznuri@...
Jul 7, 2000 5:09 am
I haven't posted this for awhile, so now seems like a good time. === I'd like to invite any new members to introduce yourself to the list. we're interested in...
1225
Vladimir Z. Nuri
vznuri@...
Jul 7, 2000 5:23 am
at times on this list I've complained that there are no good prizes for working on math problems like there have been in historical times (in the renaissance...
1226
Klaus D. Witzel
kwitzel@...
Jul 7, 2000 9:22 am
Jeffrey and Stas, thanx for your kind replies, IMHO it was a bit too much towards the education level but nevertheless you saved me introducing the CNF vs. DNF...
1227
Klaus D. Witzel
kwitzel@...
Jul 7, 2000 11:34 am
Let me try benefiting from the recent CNF vs. DNF messages here in theory edge. I intend to characterize the kind of algorithms used for SAT-3CNF problems and...
1228
Stas Busygin
busygin@...
Jul 7, 2000 2:02 pm
... Obviously. ... Not the worst if you thoroughly choose which clauses to distribute. Distributed clauses should have maximal number of common variables, ...
1229
Klaus D. Witzel
kwitzel@...
Jul 7, 2000 3:37 pm
... CNF ... Thank you, I should have said, _unconstrained_ CNF2DNF as the worst case example. ... Yeah, SAT is such a nice, surprisingly rich problem space....
1230
Dan Pehoushek
danpehous@...
Jul 7, 2000 8:07 pm
Dear Klaus, Your point is well taken, that davis-putnam and variants kind of "read off" some form of dnf, in exp time and linear space. The added efficiences...
