tag:blogger.com,1999:blog-3722233.post7903477008454080355..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: Open: PROVE the pumping and reductions can't prove every non-reg lang non-reg.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-19755047649988096502017-10-30T23:55:55.238-05:002017-10-30T23:55:55.238-05:00You're right, I haven't realized that we c...You're right, I haven't realized that we can pump zero times!domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85439213623143359582017-10-30T02:55:06.309-05:002017-10-30T02:55:06.309-05:00I said that, given the pumping length p', we c...I said that, given the pumping length p', we can pick as "reference" string w' = x'y'z' with |w'| >|p'| as string w' in which we have exactly one 2 between every 0,1 symbols. In this case, if we have a pumping string of only one 2 (i.e. y' = "2") we can pump zero times and we get a string out of the language ("... and at least one between any two original numbers ..." from your answer). So we must have at least one 0,1 in y' (and at least one 2 at the beginning or at the end). But in this case we should be able to apply the pumping lemma easily in the same manner as we apply it on the original L.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3874684342159426992017-10-28T15:55:00.078-05:002017-10-28T15:55:00.078-05:00You seem to use that in the pumped string we also ...You seem to use that in the pumped string we also have exactly one 2 in every gap, but this is not required. In fact, it's possible that we only pump a single 2.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11914507672226045032017-10-27T08:11:14.524-05:002017-10-27T08:11:14.524-05:00A pumping length p', in L' corresponds to ...A pumping length p', in L' corresponds to a pumping length p'/2 in L; indeed you can pick a string w' = x'y'z' with |w'| >|p'| in which there is only one 2 between two {0,1} symbols.<br /><br />Suppose that p' is even, then the substring y' than can be pumped must be of the form:<br /><br />1) y' = 2 (0|1) 2 ... 2 (0|1) or <br />2) y' = (0|1) 2 ... 2 (0|1) 2 or <br /><br />In every case pumping it and proving that the resulting string (which is still in the form with exactly one interleaving 2 between the 0s and 1s) falls out of L' should not be more difficult than proving it in the original L.Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82961982105064163512017-10-27T03:36:19.192-05:002017-10-27T03:36:19.192-05:00I might be wrong, but there seems to be an one eas...I might be wrong, but there seems to be an one easy way to defeat the pumping lemma as follows. For any language L over {0,1}, take the language L' that has the same words as L, except that it can contain an arbitrary number of 2's anywhere in the word, and at least one between any two original numbers, the beginning and the end. For example, 101 can be converted to 2122202222122. Whenever one tries to pump a word with these properties, it's possible that always the 2's get pumped. If you try to pump a word that doesn't have enough 2's, you might end up with one that also doesn't have enough 2's. Of course, if you don't like 2's, you can work with extended binary, and convert an original 0 to 00, 1 to 10 and 2 to 11.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78499215178876198432017-10-27T02:53:53.691-05:002017-10-27T02:53:53.691-05:00Another silly example would be to let A be a non-r...Another silly example would be to let A be a non-regular language if the Riemann hypothesis holds, and let it be empty otherwise.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78701890355544834682017-10-26T05:02:13.390-05:002017-10-26T05:02:13.390-05:00I have no idea. I would not believe I was the firs...I have no idea. I would not believe I was the first person to think of it though.Guilhermehttps://www.blogger.com/profile/16356657960297015642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78963164846567928662017-10-25T13:13:54.758-05:002017-10-25T13:13:54.758-05:00This is precisely Myhill-Nerod theorem, right?This is precisely Myhill-Nerod theorem, right?Anonymoushttps://www.blogger.com/profile/06645215757582794663noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72013174894366449182017-10-24T14:02:50.064-05:002017-10-24T14:02:50.064-05:00Let me be the defender of the pumping lemma. Here’...Let me be the defender of the pumping lemma. Here’s a good generalization: If L is regular then there is an n s.t. for x in L, if x=abc with |b|=n there is a uvw with |v|>0 such that auv^iwc is in L for all i.<br /><br />With the definition every language given by Bill can be pumped directly--no need for closure properties. It’s very hard to come up with a non-regular language that fulfills this pumping lemma.<br />Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83676793519555314242017-10-24T08:03:14.487-05:002017-10-24T08:03:14.487-05:00I'll think about more reasonable examples, but...I'll think about more reasonable examples, but clearly you can hook the non-regularity of A to some hard to "decode" (or even undecidable) functions; e.g.:<br /><br />e.g. A = { a^n | the n-th Turing machine halts after 2^n steps }<br /><br />I think it's quite hard to (formally) prove that it's not regular using the pumping lemma or other standard tools because it highly depends on the encoding.<br /><br />In other words you can "play" with the fact that unary regular languages are a union of semilinear sets (the set of exponents of the regular unary langauge is an union of semilinear sets); and if it's difficult to prove that a set B is not semilinear then it's hard to prove that the corresponding A = { a^n | n \in B} is not regular.<br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90195016815353428882017-10-24T04:01:47.897-05:002017-10-24T04:01:47.897-05:00I don't like the pumping lemma because it hide...I don't like the pumping lemma because it hides the reasoning behind a complicated lemma statement. For that reason, I avoided teaching it many times. The strategy I use when I want to show to the students that some language is not regular is the following. I define that two prefixes A and B are distinguishable if there is a string W such that AW is in the language and BW is not or vice versa. If I can show there are arbitrarily large sets of pairwise distinguishable prefixes, then the language is not regular. (The reason being that multiple prefixes would lead to the same state of the DFA, and therefore either both would accept the suffix W or reject it.) I've never thought of it, but I'd be surprised if there are nonregular languages that cannot be showed nonregular by this approach.Guilhermehttps://www.blogger.com/profile/16356657960297015642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37497921111300797132017-10-24T01:28:26.496-05:002017-10-24T01:28:26.496-05:00First note that the direction for your reduction f...First note that the direction for your reduction function f is somewhat the opposite of the usual notion which preserves easiness in the other direction. (If B is easy then A is easy.) I will use the direction you gave despite this grumbling...<br /><br />However, it is easy to resolve your question because there is a fundamental problem with your definition of reduction that makes the answer to your OPEN QUESTION a trivial NO. Let B* be a non-regular problem for which (a) does not hold. That is, the non-regularity of B* does not follow by the pumping lemma (i.e., it satisfies the pumping lemma). Let A* be any other language that is not regular that does follow by the pumping lemma (it doesn't satisfy the pumping lemma). <br /><br />Define function f on languages by:<br /><br />f(A*)=B* and if A != A* then f(A)=A.<br /><br />Clearly f preserves regularity because it satisfies an EVEN STRONGER condition: A is regular iff f(A) is regular. <br /> <br />Therefore by your definition A* <= B*. It follows that B* satisfies case (b) of your definition of being easily proven non-regular.Paul Beamehttps://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26791722146012166312017-10-23T13:54:41.965-05:002017-10-23T13:54:41.965-05:00I imagine a pretty reasonable way to define reduct...I imagine a pretty reasonable way to define reductions in this world is to say A <= B if A can be formed by regular expressions that use B as a basic set (for example A = B*{0,11}). <br /><br />For your question about poly-time Turing reductions, it's pretty clear that these two definitions are not equivalent as one lets the halting problem be reduced to any computable language outside of P whereas the other does not. If your question was meant to be "just considering pairs of languages in NP", I don't actually know if given P different from NP that there is an L in NP\P where NP doesn't poly-time Turing reduce to L (maybe Ladner's theorem or some extension shows this?), but certainly if SAT isn't in QuasiP, then SAT can't be poly-time Turing reduced to anything in QuasiP, and this would again give us a discrepancy in these two definitions.Anonymoushttps://www.blogger.com/profile/14194595139510665851noreply@blogger.com