Hi all, On the theory-edge list, Vaughan Pratt is offering a US$50 prize to the first person to solve a puzzle problem--either by offering a polynomial time...
Hi again, Let me restate this theorem from Sipser one more time: 1. An oracle A exists whereby P^A != NP^A. 2. An oracle B exists whereby P^B = NP^B. Now it's...
hi KLVE. happy new year to you too. your star student MNC defected. haha. although he never replies to my emails. I think he is just too intimidated by me.....
Hi Vlad, ... Haven't heard from Mike in a while... I'm hoping he's just away on winter break and will be back soon. ... As it turns out, the very next topic in...
hi KLVE john savage's book is very impressive, although it seems to have numerous typos, but I think he has corrected them on his web site. the book is rather ...
Hi Vlad, ... The SIGACT News is available online in PDF format, but you need to be a SIGACT member to access it. URL: http://sigact.acm.org/ . However, ...
Hi all, I'm getting a bit ahead of myself here, but since the topic has come up, let me throw out a list of possible subjects to study after Sipser has been...
Hi, Kurt and All! What about a thorough educational discussion on Lovasz's theta function and bunch of topics derived from it? I can provide a must-read list...
... I'm more interested in the pure math angle but check out Kurt Mehlhorn's home page. He's one of the principal authors of the LEDA graph library. You can...
Hi all, I'm new on this list, so maybe a little about myself. I'm studying computer science on the University of Mining and Metallurgy in Poland (the name is a...
hi KLVE. awesome list of topics. really gets my neurons going. you also told me in email once that you wanted to solve the AI problem, but that in the...
hi all. one other idea. last year I did an inquiry into some of wolframs ideas on cellular automata & have some good refs. Ive got his book. I dont know of any...
What do you mean by the AI problem? Regards, Casey...
Casey Hawthorne
caseyh@...
Jan 7, 2003 12:30 am
855
ok PF. welcome to the list. Ill bite. can you explain more on ladners theorem? have not heard of it, sounds very advanced. this probably relates to the ...
... It is just a survey of major theta-related results published up to 1992. There is also a more recent and simple overview of the topic by Michel X. Goemans...
I like all the ideas presented so far. One other area of study that I find interesting that hasn't been mentioned yet so far is finite model theory, which is ...
Hi Stas, ... function ... of ... I looked at your post on algorithm-forge and have to confess that most of it went over my head. I would need to learn a lot...
Hi, ... Well, I don't remember if that's exactly how I had put it... But anyway, there are lots of AI 'problems' (and I mean this more in the philosophical...
... Hi, I always enjoy to write about my hobby :) If B is a computable set not in P then there is a computable set A, such that 1. A not in P 2. A reduces to B...
Hi Kurt! ... I really think that the Goemans' note is easy to read and enough to understand the basics of the topic: http://www-math.mit.edu/~goemans/icm98.ps ...
... n^n doesn't grow fast enough -- my mistake. It's better to take for example: g(0) = 1 g(k) = 2^(2^g(k-1)) , k > 0 and then: A = { x : x in B and |x| =...
hi PF. I guess I had heard of ladners thm in the following form. was not aware it was more general. thanks for the info. great to run into someone who has a...
hi SB. I know what eigenvalues/vectors are etcetera as documented in your post. what I find fuzzy in my own mind (& in your descriptions) is the link to...
... No. Just take the adjacency matrix and put 1's instead of 0's on its main diagonal. Formally speaking, consider matrix A_G+I, where A_G is the adjacency...
Hi, That overview of finite model theory seems very interesting... it gives me another reason to want to learn more about logic. If I remember correctly,...
Hi Piotr, ... That's very neat, like a 'descending' hierarchy theorem. ... I'd be interested in seeing more about this, when you have the time. Thanks, Kurt...
... <pfali@s...> ... Hello everyone, I'm back after a small hiatus. I have a quite a few things I've been saving up to post, but I've been so busy lately that...
... This example is incorrect since for instance O(log f(x)),O(f(x)) are both in O(2^f(x)) and these alternating regions should be disjoint. Again, L is made...
Sorry for my belated response. And happy New Year evebody! ... <kvanette@c...>" <kvanette@c...> wrote: [...] My suggestion is to take a break before going into...
As per usual, I run out and do a (outline for a) proof, without taking in the full implications of the theorem. (note: the outlines are definitely not my...
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.
