Hi Sarika, Michael Sipser's book is very well regarded. Here is the Amazon link: http://www.amazon.com/gp/product/0534950973/ This book is not going to be...
Hello, For some strange reason I found a way to Prove that P=NP, please find my mistake: Following the PCP theorem we know that NP=PCP(O(log n),O(1)), now I'll...
... find ... I'll ... that ... 2^O ... number of ... result ... accepts Hello, there are n^O(1) coin flips we need to try, each of which may query some O(1)...
... now ... may ... (1) ... Why do I need to try each possible certificate? I know that we can asume that M' is non-adaptive and that it asks the same number...
From a quick look: You have O(log n) coin flips, and so you may have to look at a polynomial number of positions in the certificate. That's fine, provided you...
... have ... That's fine, ... from? ... where ... please ... only ... n^O ... every ... possible ... can ... Now I may got this all wrong, but doesn't the...
... one ... any ... M' ... which ... n^O ... all ... of ... queries ... I ... Good afternoon, Yap, you lookup O(1) bits in a polynomially long certificate, for...
Hello again, Does anyone know how I can prove that space(O(n^(log n))) is not a subset of BPP? i.e find a language in space(O(n^(log n))) that is not in BPP. I...
... Good night, I think we may use the space hierarchy theorem to conclude that PSPACE is a proper subset of SPACE(O(n^log n)). We then observe that BPP is a...
Hello, This is my first post here and have been reading the newsgroup for awhile. Please let me introduce myself. I studied CS in Guatemala and finished 6 ...
Hey, While this is not a main scope of this list, neither is solving homework problems and we get that a lot :) So a couple of quick comments: European...
Thank you for your answer. My interests are primarily in Complexity and Computability. ... Thank you for your answer. My interests are primarily in Complexity...
Hi people (i'm new here) This is a question I encountered in our homework, and I have not been able to solve: Assuming coNP != NP (of course this also means P...
Hi, ... Interesting problem. I haven't seen this before (although it seems like an obvious kind of question to ask), and I don't off-hand know of a way to...
Hi Kurt, I think the claim is false: Let us use alphabet E = {0,1} Let A be SAT, and let: 0A = {0x | x in SAT } 1A = {1x | x in SAT } Thus A' = 0A u 1E* is...
... e.g., ... strange to ... can send ... Thanks Piotr! It turns out that the assumption coNP != NP was misleading. Interestingly, the counter-example you gave...
... Perhaps because last semester I was TAing a very similar course :) I guess there is something in the air with us, TAs, thinking :D:D ... This actually has...
Hi, I have a question that is somewhat related to mathematics and cryptography. In RSA encryption, the method followed is to choose two large primes p and q,...
Hello, ... What leads you to this conclusion? Take, for example: p=3, q=5, n=15, e=3, d=3, and m=2. Then, c=8 and the modular inverse of c is 2. m * (modular ...
Oops! My mistake; I typed the wrong equation. I know the attacker has many pairs of (m, c), but my question is more correctly this: The discrete log problem...
... something? ... In our course we defined TQBF to be fully quantified (true) CNF formulas. Similaraly SAT is defined as satisfiable CNF formulas. So the...
... Hmm... I suppose that usually TQBF is defined over all formulas, not only CNF. What could we do in your case... The first idea is essentially to use the...
Hi all, I'm a graduating CS senior, off to study theory in graduate school next year. I'm currently making the choice of where to go. The options: Berkeley ...
Well ideally, sure. But I didn't get into MIT. So the question is, would it be a reasonable decision to go to Harvard to be in Cambridge, or would it be silly...
... I would say, now that you have "Grown up", what matters is whether you can get the right supervision in the area that you are looking to research in. Going...
Nimish Shah
Nimish_Shah@...
Mar 4, 2006 8:52 am
2290
... I agree completely. I went to the EE school on the other side of river from MIT, which wasn't as "good" as MIT. With that said, my supervisor once said...
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.
