hi all. I dont want to post much more on this thread over on theory-edge for the moment because I think its a little too technical for the crowd, but I will...
LR posts in msg #8076 on theory-edge a disproof of my challenge problem in #8076. ok, fair enough, but what LR didnt notice was that the same argument seems to...
... I'm not sure if I quite understand what sort of inconsistence do you have in mind? I will read through the theory-edge discussion and probably then will ...
hi all, I posted on theory-edge that I thought e.g. the speedup and gap theorems were far more important than the oracle relativization results. here is an...
hi all. LT just asserted on theory-edge that P^EXP == P^E. (theory-edge msg #8079) he said this was true because there is an EXP complete problem in E. maybe...
hi piotr. sorry about the typo, Ive been writing the same thing a lot of times lately and getting sloppy. my challenge problem is to prove that BGS75 is not a...
... As far as I know, the biggest difference between E and EXP is that E is not closed under many-one polynomial time reductions. When such classes are...
hi PF, I dont understand. it seems like you are getting the directions mixed up. E == exponential time with linear exponent EXP == exponential time with linear...
... Exactly. ... Let C be an EXP-complete language, solved in time 2^(n^k). Take: C' = { x0^(|x|^k): x in C } Now to test if some word y is in C' we do the...
... Yep -- after the summer holidays I'm starting my fifth (last!) year at the University of Science and Technology in Cracow, Poland. I'm staring to work on...
There seem to be a lot of misconceptions on the topic, so I'll try to clarify a few things. 1) Oracles are attached to machines, not to complexity classes If C...
... To be strict, I think TALLY is the set of languages containing only words of the form O^n, where 0 is some fixed symbol from the alphabet. I guess the...
hi PF ... this seems strange to me, and reminds me of MNC's recent questions about "reasonable encodings". you are padding exponents in unary. it seems to me...
thanks very much to LT for the long & generous writeup-- Im printing it out for future reference. maybe some comments in a bit. Ive downloaded two papers off...
I am reading "relativization, a revisionistic retrospect" by hartmanis et all published in late 80s or so, available on the BEATCS page. some very interesting ...
Hi all, ... I just uploaded [HPV77] to the files section. Enjoy! I'm not familiar with the TIME[n] != NTIME[n] paper, but it does sound intriguing. It might...
Hi again, ... I wasn't able to find this paper online anywhere, but it gets cited in a LOT of other papers which build on the results. I just uploaded one ...
... 1) DTIME[f(n)] contained in DSPACE [f(n)/log f(n)] where f(n) need not even be space constructible. 2) DTIME [f(n)] is contained in ATIME [f(n)/log f(n)] ...
http://www.cs.berkeley.edu/~aaronson/cosmology.ppt This is a completely fascinating power point presentation on the physical limits of computation. Things...
hi all, I am again wondering about the proof that there is an EXP complete problem in E. my question, why cant the same reasoning/approach be used to show...
hi all, I was just looking over hopcroft/ullman again, and they prove the speedup theorem for space, not for time, .. so I am wondering, does it hold for time?...
while we are talking about BGS75, contradictory relativization for P vs NP. I went back & looked at the proof in hopcroft + ullman & would be curious about ...
I am looking over LTs notes on oracles. thanks again for the clarifications.. however, some objections, I hope to read any responses or ideally LTs own if he...
thanks KLVE. the surprising thing is that I thought all this time P =? PSPACE was an open question but P != PSPACE seems to follow from the theorem, but yet...
Hi Vlad, I had been looking at HPV77 a few months ago (out of an interest in space/time trade-offs, something we share in common), so when you cited it I...
Hello VZ. So you finally went through the (BGS75) proof eh? You should now be able to digest the proof I did that NP^C != coNP^C. For an overview of the...
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.
