Theory
in [Programming]
|
This year's Godel Prize http://opa.yale.edu/news/article.aspx?id=5937 Anyone know what the significance of this is? I didn't really gather from the article what they were talking about, or why it was so important. ... 15 Aug 2008 22:19
B tree hi all i'm learning data structures and i have a question regarding b-trees. suppose we have 2 B-trees: A and B, both of order m. one has a keys and the other b keys. we know that all the keys in A are smaller than the keys in B. how can we make one B tree of order m out of both of them in O(log(max(a,b))? ... 14 Aug 2008 01:09
The Computable Reals (alpha version) The Computable Reals (alpha version) ------------------------------------ Julio Di Egidio (JDE) julio at diegidio dot name (c)2008 JDE, on behalf of sci.math, sci.logic All right reserved. ============================================= I will try to give a construction for the "computable reals". We are go... 10 Sep 2008 14:29
Another approach to decide on existence of a real root for Univariate Polynomials with Integer Coefficients, and a possible Multivariate extension for 3-SAT I just want to inform you, that I will certainly be able to finish my Version_5 of my arXiv:0803.0018 paper, before end of August 2008. I promise that I will not delay any more. You may just note that in my Version_5, my Theorems 6 & 7 will be removed (as Dr Moews has refuted them), and they will be replaced by a... 12 Aug 2008 02:56
3SAT - A Counting Solver I describe a new back-tracking SAT solver. I described a similar SAT solver several years ago. I think I called the earlier one the Simple SAT solver. The Simple SAT solver was very slow, but this one should be much faster. The basic idea is simple. Assume we have a 3SAT instance with n variables. Assume each ... 15 Aug 2008 04:50
Graph representation compress Hi theory guru! I am interested in compress large (spare/complete) (static/dynamic) graph model representation. What data structures helps to represent graph with 10.000.000 and more vertexes as compress as possible. And what data structures provide high performance factor for such graphs? Maybe, it ll be coded ad... 12 Aug 2008 00:54
halting problem proof, via diagonalization? I heard someone say recently, "The proof of the Turing machine halting problem is an example of diagonalization." I don't see that. As I recall, it's proof by contradiction; assume a program which accomplishes the goal, feed the code of this program to itself, etc., ad absurdum. QED Whereas diagonalization c... 15 Aug 2008 01:47
How to do this? Hi, In a code, how can you check if a word is "verb" for example? Thanks, Mike ... 6 Aug 2008 06:39
Can EXPTIME and NP be separated via diagonalization? Hi, I was wondering if it might be possible to separate EXPTIME and NP via diagonalization. I ask because I cannot think of an oracle A such that EXPTIME^A = NP^A. (I don't think an EXPTIME-complete problem would work, would it?) Has there been a result akin to the Baker-Gill- Solovay result for EXPTIME and... 7 Aug 2008 14:30
Java based sat solver Hi, this is my n-th try for a sat solver: http://tokisworld.org/sat/SATConverter.jar Solver 4 can solve the factorization problem for 5 bits, as well as these problems : http://www.cs.ubc.ca/~hoos/SATLIB/Benchmarks/SAT/GCP/flat30-60.tar.gz http://www.cs.ubc.ca/~hoos/SATLIB/Benchmarks/SAT/GCP/flat50-115.tar.gz ... 2 Aug 2008 10:29 |