tag:blogger.com,1999:blog-3722233.post6386185179971179894..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: Reductions between formal languagesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-19842548108187514552017-10-18T16:22:28.994-05:002017-10-18T16:22:28.994-05:00We can show that EQ0 is not regular using only com...We can show that EQ0 is not regular using only communication complexity tools in this way: if EQ0 is regular, then we can obtain on O(1) comm protocol for EQ (which is false)<br /><br />- Suppose that w = xy; Alice knows x and Bob knows y<br />- Suppose that EQ0 is regular so, there is a DFA D that recognizes a^n b^n.<br />- We give D to both Alice and Bob.<br />- Then Alice calculates n = 2^#a * 3^#b where #a, #b are the number of a and b in her x<br />- Alice runs D on a^n and communicates the final state q_i to Bob (in constant time)<br />- Now Bob can simulate the behaviour of D starting from state q_i and inputs b,bb,bbb,bbbb,... until he founds b^k that is accepted by D<br />- By hypothesis D recognizes EQ0 so k is exactly the n constructed by Alice<br />- By the prime number theorem he can recover #a and #b from n<br />- Then he can count the #a' #b' that occur in his string y and check that #a + #a' = #b + #b' and can answer correctly to the EQ problem.<br />- Clearly the communication between Alice and Bob is costant (it only depends on the fixed D)<br />- So we proved that EQ has constant comm complexity which is a contradiction<br /><br />A slightly variant is the following: Alice computes n = |#a - #b| and transmits to Bob the state q_i of D after parsing a^n, plus a flag bit which is 1 if #a >= #b. As above, Bob can reconstruct n and check that ( #a >= #b and #b'- #a' = n ) or ( #a < #b and #a' - #b' = n).Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29469861670378646512017-10-17T08:55:14.795-05:002017-10-17T08:55:14.795-05:00Narad- thanks for Comm Comp Proof!
David and Paul...Narad- thanks for Comm Comp Proof!<br /><br />David and Paul- I've been hearing comments like `Puming lemma is lousy, Myhill or Kolm is much better' for a while now and I am<br />trying to put such statements on a rigorous basis by looking at<br />all ways to prove things not regular and also include reductions.<br />My goal is to get a language that you CAN prove not reg by<br />Myhll Nerode or Kolm but CANNOT prove rig by pumping AND closure.<br />Pumping is ambigous since there have been many pumping lemmas.<br />ANYWAY, I'll be postong on that at a later point.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4280579498826865282017-10-17T00:26:37.861-05:002017-10-17T00:26:37.861-05:00It seems that the issue for EQ0 is one of uniformi...It seems that the issue for EQ0 is one of uniformity. CC is a non-uniform model of computation. The natural relationship of CC to DFAs for a language L is for the family of languages <br />L intersect Sigma^n. In this case what we get are oblivious read-once BPs (i.e. OBDDs) with the fixed input order. Obviously also one cannot do this with a constant # of states, but another natural non-uniform analogue with the # of states is the width. This is what CC bounds and of course, EQ0 is computable by constant width OBDDs.<br /><br />On the other hand, the pumping lemma is a lousy tool that doesn't always work. Why not use the easy direction of the Myhll-Nerode theorem which is both completely intuitive and always works?Paul Beamehttps://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26371768036196303732017-10-16T21:12:29.308-05:002017-10-16T21:12:29.308-05:00Why not just Myhill Nerode directly to show EQ is ...Why not just Myhill Nerode directly to show EQ is not regular? It is so direct: the suffix set corresponding to prefix a^i is distinct for each integer i. (For example it contains b^j iff i=j)<br />Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54072602118606731152017-10-16T14:18:25.986-05:002017-10-16T14:18:25.986-05:00I think that you can still get an O(1) protocol fo...I think that you can still get an O(1) protocol for EQH with a putative EQO DFA. Let M be such a DFA. Alice counts the number of a's in x. Let this count be m. Now Alice transmits m to Bob using O(1) bits as follows. Alice feeds a^m to her EQO DFA and records the state q that is reached. Alice sends M and q to Bob. Bob starts feeding b's to M starting from state q until M accepts. Bob counts the number of b's it took, which must equal m.<br /><br />You can play the same game with Kolmogorov complexity. Li and Vitanyi do this in their book (Jeffrey Shallit also has this approach in his book as well).Narad Rampersadnoreply@blogger.com