Surreal numbers are wonderful, and I have been looking for applications for them for a long time. You can read about them in "On Numbers and Games" (Berlekamp...
516
Vladimir Z. Nuri
vznuri@...
Mar 3, 1999 1:00 am
springer verlag: I think I just posted the CS url.. they just sent me info on a reorganized math section.. ... Date: Tue, 2 Mar 99 14:21:43 -0500 From:...
517
Anatoly D. Plotnikov
aplot@...
Mar 4, 1999 2:03 pm
Let Z_1 and Z_2 are computational models of NP problems. Let Z_1 and Z_2 be the NP-hard problems. Suppose, for each instance I_2 of a problem Z_2 THERE EXISTS...
518
Anatoly D. Plotnikov
aplot@...
Mar 5, 1999 4:39 am
Dear colleagues, I would like to announce the following result. The abstract of my new paper be: For arbitrary undirected graph G, we are designing...
519
Vladimir Z. Nuri
vznuri@...
Mar 5, 1999 4:46 am
Anatoly-- converting one problem to another with a proof that "there exists" a correspondence is alone not very useful. there is probably some sense that just...
520
Anatoly D. Plotnikov
aplot@...
Mar 5, 1999 7:00 am
... The minimum cardinality covering problem (MCCP) is NP-complete. For any MCCP, we may construct a monotone Boolean expression (Petrik's method). An...
521
Derik Hawley.
dhawley@...
Mar 5, 1999 3:55 pm
O(n log n) means the Run time is proportional to (n * log (base2)n). Where n is the order in the case of graph algorithms. ... eGroup home:...
522
Saurabh Mathur
saurabhm@...
Mar 5, 1999 4:14 pm
To be more precise: O(n lon n) means that the running time of the algorithm has an upper bound of n*log(n) I dont think the base matters..you can always...
523
Anatoly D. Plotnikov
aplot@...
Mar 5, 1999 4:21 pm
... Thus, you believe that this is a running time. Hence, there exists SAT for HCP having at most O(n log n) Booolean operations. Who knowns similar SAT? Are...
524
Vladimir Z. Nuri
vznuri@...
Mar 7, 1999 6:26 am
A writes ... I'm not following.. are you saying there is a polynomial time solution to MCCP and MCCP is NP complete? you seem to be saying there is a...
525
Anatoly D. Plotnikov
aplot@...
Mar 7, 1999 8:39 am
... Since we consider the computational model of a constructive combinatorial problem then we must point out on different understanding of the term "solution"...
526
John.Tromp@...
Mar 7, 1999 4:33 pm
... I assumed n would be the either the number of edges (normally denoted m) or the number of bits needed to describe the graph, which would be of the order...
527
Anatoly D. Plotnikov
aplot@...
Mar 8, 1999 1:13 pm
The announced paper "Designing SAT for HCP" is available through the URL http://xxx.lanl.gov/abs/cs/9903006. ... I think that it is a good lower bound....
528
Vladimir Z. Nuri
vznuri@...
Mar 8, 1999 10:04 pm
Anatoly.. am not totally following your ideas, but I do congratulate you on getting your paper into the los alamos archives, xxx.lanl.gov. I think they are an...
529
adall@...
Mar 9, 1999 2:03 pm
I was working on Lindenmayer Systems (L-systems)and came up on the subject of Indexed Languages, which are basically a (context free) generalisation of CFG's....
530
Derik Hawley.
dhawley@...
Mar 9, 1999 8:25 pm
Hello, Genetic Algorithms are something I do not know much about. A person in the same lab as I was did a genetic algorithm for Attributed Graph Isomorphism, ...
531
Cris Moore
moore@...
Mar 9, 1999 9:16 pm
You might enjoy the following: ``Queues, Stacks, and Transcendentality at the Transition to Chaos.'' (with Porus Lakdawala) Submitted to Physica D. available...
532
Vladimir Z. Nuri
vznuri@...
Mar 10, 1999 11:57 pm
Derik: there is actually some new thinking in genetics that suggests that there are a lot of hardwired (DNA) traits that are not expressed, but when the...
533
Klaus D. Witzel
kwitzel@...
Mar 13, 1999 2:52 pm
Dear all, I would like to discuss a strange result I found when trying to "reduce" CNF boolean expression to DNF (regardless of time and space complexity, just...
534
Anatoly D. Plotnikov
aplot@...
Mar 13, 1999 8:57 pm
... I think that the discussion in groups, which are similar theory-edge, have difficulties due to the fact that the members of the group have a different ...
535
Derik Hawley.
dhawley@...
Mar 13, 1999 9:17 pm
... I think this is a good idea, alot of things can benefit from working out a simple explanation of the problem. Even an expert can notice something when ...
536
Vladimir Z. Nuri
vznuri@...
Mar 14, 1999 5:07 am
its a big struggle to connect with other people in general, but in theoretical areas communication is even more difficult.. the term "balkanization" might...
537
Vladimir Z. Nuri
vznuri@...
Mar 14, 1999 5:12 am
Klaus-- there are multiple equivalent DNF expressions for a given CNF. (in fact finding the smallest is quite a difficult problem). however if the CNF is...
538
Anatoly D. Plotnikov
aplot@...
Mar 14, 1999 8:30 am
Thank you to Derik for the support. I agree with Vladimir that there are difficulties for people when English is not the first language for their. It will be...
539
Anatoly D. Plotnikov
aplot@...
Mar 16, 1999 5:12 am
I have received information from the same source ("...there exists an O(n log n) from HCP to SAT..."). There is the paper "SAT-variable complexity of hard...
540
Klaus D. Witzel
kwitzel@...
Mar 16, 1999 1:25 pm
One of the authors can be located at http://www.lab2.kuis.kyoto-u.ac.jp/~iwama/ perhaps an email to him reveals where his paper is available online. ... ...
541
Anatoly D. Plotnikov
aplot@...
Mar 17, 1999 4:51 pm
Hello everyone, Just now I have received a tex-file of the paper "SAT-variable complexity of hard combinatorial problems" by Iwama k., Miyazaki S. I think that...
542
Anatoly D. Plotnikov
aplot@...
Mar 18, 1999 6:59 pm
Hello everyone, Yes, there exists the reduction from HCP to SAT in the paper "SAT-variable..." using O(n log n) variables. This is a many-one reduction. Note...
543
Anatoly D. Plotnikov
aplot@...
Mar 20, 1999 10:18 pm
To be available on-line, I place the paper "Formalization of the class of problems solvable by a nondeterministic Turing machine" in ...
544
Naveen Rao
nrao@...
Mar 22, 1999 5:29 pm
Hi In the April 1999 issue of Scientific American there is an article titled "Alan Turing's Forgotten Ideas in Computer Science" which is worth reading. It...
