Hi all, I'm new here and this is my first post, hoping it would be helpful. My problem is in relativization of the P=NP question. I've read the proof about the...
Hi Cuchc, ... I haven't looked at this in a while and don't remember the details off the top of my head, but this should give you the general idea... You have...
Thanks, you've been very helpful! The only problem I have left is that when I diagonalize over all NP^A machines I have to know how they would respond to a...
... NP^A machines I have to know how they would respond to a given input on every non-determinstic path (so I'd know what to put in A) - which take exponential...
Now it all adds up. Thank you Kurt. ... NP^A machines I have to know how they would respond to a given input on every non-determinstic path (so I'd know what...
Hi all, I know that the following is wrong but I don't know why: I want to build a language in EXP\BPP by diagonalizing over BPP macheines so I came up with...
... To diagonalize against n^3 time machines, in this step we may need to construct trees of depth up to n^3. This shows BPTIME(n^3) != EXP. Constructing trees...
Hi, I have started a new group name "Statisticians_group" in the yahoo group for statisticians or the persons who are interested in statistics. The URL is...
hi every one, recently i noticed connectionist models of computing that are related to almost every thing, logic, computability, nuro science, complexity and...
hi all, another wild idea for you. I wonder if there has been discussion about the union thm here. dont recall if there has been. have to search archives. I...
Free Software Tutorials(C,C++,JAVA, Database, Python, PHP,HTML,SQL ,etc. ) I have listed free tutorials available online for C,C++,JAVA, Database, Python,...
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...
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.
