It actually looks like *worse* than the usual. I like the part where they claim complexity O(m) independently of n, but later admitting their circuit has 2^n...
hi KLVE Ive studied natural proofs on and off quite a bit & can discuss it further. (ps I only scan this group once in awhile but if a thread is going Im...
hi all, earlier I was trying to articulate the idea that there might be different kinds of "infinities" or "densities" of the different kinds of languages in...
Hello all, I would appreciate any answers to the following questions: Is the General Number Field Sieve algorithm (which is said to be the fastest non-quantum...
Hi! I'm not very familiar with the GNFS, but from my point of view they are deterministic in the sense, that they use a general fixed strategy of how they work...
Thank you, and please let me ask it this way: Does the GNFS have a nonzero probability of making an error; i.e., failing to find a true factor in a single ...
The pure version is deterministic, thus always finds a correct solution. The heuristic elements do not change this, they just make change the time needed to...
Hi, I believe that BFD (best fit decreasing) one known good algorithm for bin packing (work better than BFI etc). Can you please tell me any more good...
Once again, thank you very much, and to overdo it, let me ask one more question: Is the difference between this average complexity and worst case complexity...
Some good algorithms: http://www.diku.dk/~pisinger/ ... __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the...
Such a converter may be excellent for some sort of millipede experiment, where a pin head leads many feet. ooooooooooooooooo Different topic: Any of you folks...
I work in the area of Theoretical Computer Science specially with reference to Neural Networks. But that does not restrict me to that field alone. I believe...
Two things I would like to point here : I work in the area of Theoretical Computer Science specially with reference to Neural Networks. But that does not...
... It does deserve consideration. Boxes can do mulitplies and divides so well, shouldn't they be given other opportunities? Daniel ... Do you Yahoo!? Yahoo!...
Neil Immerman has won the Godel prize in 1995 for the paper,"Nondeterministic space is closed under complementation",SIAM Journal on Computing 17 (1988),...
Hello all, Just a quick question. I have a feeling I have known this for a while, but I just can't seem to convince myself of it. Can we have a non-recursive...
I am just extending your problem and proving : We might take PA to contain the Gödel numbers of true sentences of Peano Arithmetic. By Tarski’s theorem,...
Yes, but the set is recursively enumerable. So let me sharpen my question a bit: Do there exist sets extending PA which are not recursively enumerable and yet...
everett piper <toolradiohead2@y...> wrote: EP>> Do there exist sets extending PA which are not recursively enumerable and yet still incomplete. Presumably such...
Thanks for your reply. However, I am looking for something stronger. My choice of PA as base theory is inessential, meaning I could have just used ZF or ZFC ...
Hello everyone! My purpose of joining this group is to gain some knowledge on Theory of Computing. It's my first time now to teach Theory of Computing and i...
hi dan I am still blocked on algorithm-forge so cant get to your new stuff on qbfs. can you put it up on a web site somewhere? here is a descr of a very hard...
Hi Vlad. Long time no argue :) How have you been? Still in Colorado? I am thinking about heading back out there. I am in Maine currently, attempting to wave...
THe follwoing questions are from Automata 1..Define what one might mean by properly nested parenthesis structures involving two kinds of parenthesis, say...
hi dan yes I still live in denver. what do you mean "wave your hands in front of MIT folks"? you are corresponding with them? want to get into MIT? who is...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
