It's really amazing how my teacher picks so many exercise from this book! :) ... This was a homework problem ;-) Papadimitriou shows this quite well.. it isn't...
... A hint I've found is that this can be done with a dynamical programming algorithm. It isn't immediately obvious to me. ... This has been worked out by...
Lieven Marchand
mal@...
Mar 2, 2002 9:40 pm
439
Hi Lieven, ... are ... Garey and Johnson give an algorithm for this. When I have a chance I'll look it up if no one else posts an answer first. ... Riemann ...
Hi all, Let me try my hand at answering one of the problems that hasn't provoked any comments yet: 7.25 Let U = {<M,x,1^t> | M is an NTM that accepts input x...
... 7.29 is indeed obvious, Choose variable t_i, check whether phi with t_i substituted as true is satisfiable, if so set t_i true, otherwise set t_i false,...
Lieven Marchand
mal@...
Mar 3, 2002 5:56 pm
442
Hi all, Ok, time to work another problem. 7.28 Show that if P=NP, we can factor integers in polynomial time. I think Marc's comment about this one was a red...
Sorry, I joined late. I would appreciate knowing the exact "Sipser" reference which is being discussed in this list. Is there an archives where I can see the...
... Given a possible prime n, you can do a calculation for any number a < n, such that if n is prime, the calculation gives 1 and if n is composite it gives 1...
Lieven Marchand
mal@...
Mar 5, 2002 8:11 pm
445
Hi Partha, ... archives ... topic ? Yahoo Groups has a website that you can use to view archives for all of its groups. The URL for the comp-sci-theory group...
Hi everyone, For week 27 we cover begin chaper 8, "Space Complexity" with sections 8.1, "Savitch's Theorem", and 8.2, "The Class PSpace". BTW, there are...
... Does he also cover the interesting LIN-SPACE problem? It is equivalent to the open problem of the equivalence of deterministic and non-deterministic linear...
Lieven Marchand
mal@...
Mar 9, 2002 10:40 pm
448
Hi Lieven, ... equivalent ... No, I don't think I saw it mentioned in the text. ... Well, later in the chapter when Sipser covers log space (L) and ...
... Yes. A result by Immerman and Szelepcs\'enyi. BTW: I didn't see any reply to your questions about the proof of Savitch's theorem. I agree it is kind of...
Lieven Marchand
mal@...
Mar 11, 2002 6:33 pm
450
Hi Lieven, ... Savitch's ... Are ... n? ... Presumably Sipser wanted to keep things simple so he only proves that NL=coNL, but I'm surprised he doesn't even...
http://www-math.mit.edu/~sipser/18404/18.404.html Good golly, miss Molly! -- orcmid ... Dennis E. Hamilton http://orcmid.com/ mailto:dennis.hamilton@... ...
Hi Dennis, ... Thanks for the link! Unfortunately the solution sets are not accessible outside of MIT. I'm not sure what the difference is between course...
... Ok. Let's start this. I'll do it piecewise since I don't have the time to do it in one chunk either. Theorem: For any function f(n)>=n, PSPACE(f(n)) =...
Lieven Marchand
mal@...
Mar 13, 2002 9:28 pm
454
... time ... I'm eager to see how this turns out, because the set up is a little different from what Sipser does in the text. (I'll give Sipser's version...
Hi all, I noticed an ad on comp.theory for a new complexity theory text, which looks like it might be interesting to have as a reference covering advanced...
... I doubt it. Let's get on with it though. Keeping the graph I outlined in my previous mail in mind, for any starting configuration, the question is, can it...
Lieven Marchand
mal@...
Mar 20, 2002 8:38 pm
457
Hi everyone, Sorry I've been away from the group for so long. I got sick again (or maybe it was a relapse of what I had earlier), and after that my PC was out...
hi all. does anyone have hopcroft & ullman, intro to automata,languages,& computation? I would like to discuss/question a proof. I dont know if it is in...
Hi Vlad, First off, let me say thanks for your post. I've been having trouble getting back into gear after being away from this group for a while, and this is...
Which edition of H-U? The old one is what, 20 years old? There is a new one that I haven't seen yet, although I am considering adopting it for my course in...
Lawrence L Larmore
larmore@...
Apr 20, 2002 3:54 pm
461
hi LLL. I suppose you guys like to study monte carlo methods there in los vegas CS. :p old version of hopcroft ullman. still used by a lot of people. new...
Hi Vlad, ... Why? Certainly that is the practice in contemporary treatments, but in fact H&U do define their complexity classes in terms of exact # of steps...
hi KLVE. you have to define complexity classes in terms of big-O O(f(n)) or it will lead to contradictions. you cannot define a complexity class in terms of an...
Hi again, ... Hmmm....sorry, I don't see the contradiction. Perhaps you could elucidate. Since H&U define complexity classes in terms of exact numbers of...
haha geez. I figured I would have to write it all out. partly I realized this because a long time ago I was trying to look for traps in the formality of...
Hi Vlad, ... Sorry, but there is no contradiction here. "Linear time class" refers to a collection of problems, not to specific algorithms (or TMs) for...
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.
