... The simpler version of the problem, i.e., there is a TM that decides in O(n) time, can be proved using a crossing-sequence type argument. The o(n log n)...
Lawrence L Larmore
larmore@...
Feb 1, 2002 1:56 pm
375
Hi, Someone on comp.theory has posted a reference for this. It's: Computational Complexity (Mathematics and Its Applications) by K. Wagner and G. Wechsung. I...
A site with crossing sequence questions ... Regards, Casey...
Casey Hawthorne
caseyh@...
Feb 3, 2002 4:57 am
377
Another site with a crossing sequence question ... Regards, Casey...
Casey Hawthorne
caseyh@...
Feb 3, 2002 5:57 am
378
Hi Casey, Thanks for the links. I always find it interesting (and more than a little humbling) to see what kind of material students in theory courses are...
... From comp.theory posted by Swarat Chaudhuri try recognizing {0^n1^n: n \geq 0} in o(n log n) [yes, small-o] time. can you do it? what does that tell you? ...
Casey Hawthorne
caseyh@...
Feb 4, 2002 11:55 pm
380
Hi Casey, ... Wait a minute, you just posted a link to a PROOF of this theorem, now you're going to post counter-examples?! ... time. ... Well, what it tells...
Hi, ... This doesn't help the proof posed in Sipser: If A can be decided by a single tape TM in o(n log n), then A is regular. L = {0^n1^n | n > 0} is not a...
Think of the number of the minimum number of operations needed to do a comparison based sort - which is O(nlgn). With fewer operations than that - you will not...
Casey Hawthorne
caseyh@...
Feb 5, 2002 5:10 pm
383
... Are there similar type results for languages accepted by: pushdown automata? deterministic? nondeterministic? Regards, Casey...
Casey Hawthorne
caseyh@...
Feb 5, 2002 5:38 pm
384
Hi Casey, ... on ... Well, I don't know. Maybe they are and maybe they aren't. I'm not trying to nitpick here, but this statement is just too vague to be ...
Hi everyone, This week we cover section 7.3 in Sipser, "The class NP". This will also bring us to one of the central questions in complexity theory. Sipser...
Hi all, I've heard people express a preference for one or the other definition of the class NP, and I was just curious if any of you have a strong preference...
Depends on the unsolved proof: P == NP? If P != NP, then I don't think there's a difference between NP and EXP. If P == NP, then we're asking is there another ...
Hi Marc, ... mean, ... intuitive. Well, this is exactly what I mean. Personally I find non-deterministic TMs difficult to grasp on an intuitive level, which ...
Hi, ... Well, in the hierarchy: P <= NP <= EXPTIME, P is a proper subset of EXPTIME. Therefore if it turns out that P = NP, this would imply that NP <...
[David} ... [George] This is interesting :-) I need to test my understanding of this. The idea seems to be n^k < n^log(n) = 2^(log(n)^2) < 2^(cn) Because...
hi KLVE. indeed there seems to be a bazillion ways of defining NP. think of every NP complete problem as an alternative defn of NP, and then suddenly it seems...
Hi VZ! ... But I fail to see how it can be that if all the ways of defn NP are similar then how could there be one that is more powerful & lead to the...
Hi George, ... in ... You're over-reaching a bit when hypothesizing that anything 'sublinear' in the exponent is going to lie in the middle term of the ...
I might be ahead of your readings, but here's an interesting problem. I love these kind of problems... they really get you thinking... wrack your mind, so to...
Hi Marc, If you like tackling difficult problems, you might want to take a look at a few problems from chapter 6 in Sipser that we haven't answered yet:...
Kurt, ... Okeydoke.. I will ;-) thanks! ... Ack! How ingenius! (and obvious-- just kidding). Only one problem, right... what if g computes exponentially (in...
Do any of you know if "Instructor's Manual for Sipser's Introduction to the Theory of Computation" is available anywhere? Apparently, it was published... but I...
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.
