Hi, I'm reading a proof of Toda'a theorem about PH <= P^#P, and they use in it a reduction from QBFk to a circuit in AC0 without any explanations. Can anyone...
... <cuchchcucc@y...> ... use ... good ... Thanks, but I found nothin there about the tranistion from QBFk (quantified boolean formulas with k alternating...
hi "cuchchcucc", imho todas thm is one of the most advanced areas of cs. it is not even taught in many graduate level classes.. which I presume you are--...
Hello friends, I am taking a automata class in this spring 2006 semester.I am having the book 'Introduction to languages and theory of computation--John...
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...
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.
