Hello everyone, One of largest spesialists in Graph Theory of the former USSR have written to me recently (in my translation): Now, it is accepted to include...
1329
Klaus D. Witzel
kwitzel@...
Sep 1, 2000 2:29 pm
Anatoly, you can find, with regards to Minimum Graph Coloring, the statement "This problem is known to be NP-hard [9], " @ ...
1330
Michiro Nasu
nasukun@...
Sep 1, 2000 5:52 pm
Hi Stas and all! I wrote in my mail Sent: Wednesday, August 30, 2000 10:27 AM, ... Well, Let's begin. Here are 2 definitions of SAT01 problem. I received them...
1331
Stas Busygin
busygin@...
Sep 1, 2000 10:46 pm
Hello Anatoly, and All! Please read theorem 5 of the following online text: http://www.cs.engr.uky.edu/~lewis/cs-heuristic/text/class/more-np.html I hope it's...
1332
Michiro Nasu
nasukun@...
Sep 2, 2000 10:00 am
Hi Stas! i wrote, ... sorry! i must pay for you. i was perpefctly mistaken. you are right. HCP can be easily transformed to SAT01. it can be done by just only...
1333
Michiro Nasu
nasukun@...
Sep 3, 2000 10:06 am
Hi Stas! i wrote, (... slightly modified) ... RISP can solve SISO(Subgraph Isomorphism Problem). SISO is known as NP-Complete. < SISO > input: undirected graph...
1334
Michiro Nasu
nasukun@...
Sep 4, 2000 12:48 am
Hi Stas and all! i wrote, ... but i still have one homework to be finished. i want to make an equivalent machine model for RISP. < Endless Tape Machine for...
1335
Vladimir Z. Nuri
vznuri@...
Sep 7, 2000 5:29 am
recent events on this list have sparked my brain on a particular subject related to scientific progress, namely scientific rivalries. a new book with the...
1336
Klaus D. Witzel
kwitzel@...
Sep 7, 2000 1:44 pm
Dear fellow theorists, may I draw you attention on the PhD thesis below. The author has put together a comprehensive paper, is targeting P vs. NP and has some ...
1337
Tom Morrisette
eiffelpgmr@...
Sep 8, 2000 2:28 pm
This is my first posting to this list. I discovered it a couple of weeks ago, and have enjoyed browsing your archives. Thanks to all for thought provoking...
1338
Klaus D. Witzel
kwitzel@...
Sep 8, 2000 2:48 pm
From: "Tom Morrisette" <eiffelpgmr@...> ... Welcome Tom, enjoy our "cirle". ... I'd suggest you start with the "aim-*" family and then go try the...
1339
Tom Morrisette
eiffelpgmr@...
Sep 8, 2000 2:52 pm
This was my first note. Since I wrote it, I've downloaded quite a few papers from the net. Based on my investigations, I'm even more convinced that my...
1340
Michiro Nasu
nasukun@...
Sep 8, 2000 3:14 pm
Hi Klaus and all! you wrote, ... thanks Klaus! although i'm not a theorist..., the paper was surely very interesting and useful. the author concluded that...
1341
Tom Morrisette
eiffelpgmr@...
Sep 8, 2000 3:17 pm
Date: Thu, 07 Sep 2000 08:32:55 PDT From: "Tom Morrisette" <eiffelpgmr@...> To: "Vladimir Z. Nuri" <vznuri@...> Subject: Re: New(?)...
1342
Vladimir Z. Nuri
vznuri@...
Sep 8, 2000 11:00 pm
MN ... hi MN. if you write something like this please be very careful & specific, ok? are you saying they are claiming to have a proof? or that they have...
1343
Vladimir Z. Nuri
vznuri@...
Sep 8, 2000 11:39 pm
hi tom, welcome to the group. your emails spur some musings. - secrecy & money I see many people here think there is something to be gained from secrecy in...
1344
Vladimir Z. Nuri
vznuri@...
Sep 8, 2000 11:50 pm
hi everyone. here is a very neat article on the problem of protein folding, very much at the forefront of biotechnology research, perhaps the core problem!...
1345
Stas Busygin
busygin@...
Sep 9, 2000 12:41 am
Hi Tom! Glad to meet yet another NP researcher here! Could you clarify one your assertion? ... Does it mean that if the task is only to decide is an instance ...
1346
Michiro Nasu
nasukun@...
Sep 9, 2000 2:08 am
Hi Vlad! i'm grateful for your kind advise. you wrote, ... the central theorem, "NP-complete problem X is in \DELTIME" must be proved. of course it has not yet...
1347
Rune Bang Lyngsoe
rlyngsoe@...
Sep 9, 2000 4:32 am
... Though they do have their limits. From the article: ``Le Grand and his colleagues say they'd like to let other computer users modify Folderol's source...
1348
Tom Morrisette
eiffelpgmr@...
Sep 11, 2000 5:06 am
... Thanks, Stas ... new ... nearly ... the ... problem, it ... two ... the ... First, I mistyped above. I meant to say that "The resulting binary tree of...
1349
Klaus D. Witzel
kwitzel@...
Sep 11, 2000 9:13 am
From: "Tom Morrisette" <eiffelpgmr@...> Sent: Monday, September 11, 2000 07:06 ... This sounds familiar to me, establing a R(O)BDD [Binary Decision...
1350
rsantana
rsantana@...
Sep 11, 2000 12:29 pm
Hi all, I am working on my PhD thesis about heuristic algorithms for problems defined on graphs. I have not been able to find information about the time...
1351
Tom Morrisette
eiffelpgmr@...
Sep 11, 2000 2:22 pm
... wrote: -- snippet deleted ... Diagram] in ... has ... I'm pretty sure this is quite different from my approach. I'm applying something very much like the...
1352
Tom Morrisette
eiffelpgmr@...
Sep 11, 2000 2:56 pm
... -- snippet deleted ... graphs an NP one ... Nice problem! It's "obvious" to me that the maximal dissection has exactly as many components as the maximal...
1353
Klaus D. Witzel
kwitzel@...
Sep 12, 2000 7:17 am
From: "Tom Morrisette" <eiffelpgmr@...> Sent: Monday, September 11, 2000 16:22 ... Intro to BDD and a pointer to BED: ...
1354
Tom Morrisette
eiffelpgmr@...
Sep 12, 2000 1:57 pm
I haven't thought about how to determine whether a dissection exists. If that is an issue, please reply saying so, and I'll think about it. I don't think ...
1355
rsantana
rsantana@...
Sep 12, 2000 4:11 pm
... Thanks for references on Micali & Vazirani's work. -- snippet deleted...
1356
Tom Morrisette
eiffelpgmr@...
Sep 12, 2000 5:27 pm
... -- snippet deleted ... Perhaps I misunderstood your original question. When you asked about "the dissection problem for arbitrary k", did you mean "is...
1357
Michiro Nasu
nasukun@...
Sep 12, 2000 5:43 pm
Hi Roberto! ... very fancy problem! where did you find such a problem? i don't know whether this is NP or P, but i conjecture is P. when k=0 the dissection...
