4
$\begingroup$

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication complexity $c(m),$ and we let $L = \{ij \mid g(i,j) = 1\}.$

Would it be accurate to say that if $c(m) = O(1),$ then $L$ is regular? I'm not entirely sure that this is the case. I've been trying to think about counterexamples to this statement, but I can't really think of any. I do know that the converse is true, namely that if $L$ is regular, then $c(m) = O(1)$. I've been racking my brain over this in the past few days. Any ideas?

$\endgroup$
2
  • 1
    $\begingroup$ Please do not delete a question after you have received an useful response. We want to keep your question and any answers to them, so that we do not only help you, but also others with a similar question. $\endgroup$
    – Discrete lizard
    Oct 9 '20 at 8:23
  • 1
    $\begingroup$ Please don't vandalize your posts. By posting on the Stack Exchange network, you've granted a non-revocable right, under the CC BY-SA 4.0 license, for Stack Exchange to distribute that content (i.e. regardless of your future choices). By Stack Exchange policy, the non-vandalized version of the post is the one which is distributed, and thus, any vandalism will be reverted. If you want to know more about deleting a post please see: How does deleting work? $\endgroup$
    – cigien
    Jun 27 at 2:51
3
$\begingroup$

No. Let $L_0$ be a context-free language, say the language of matched parentheses, $L_1 = \Sigma^* \setminus L_0$, and

$$L = \{ij \mid b \in \{0,1\}, i \in L_b, j \in L_b, |i|=|j|\}.$$

Then $L$ is not regular, but it has communication complexity $O(1)$.

$\endgroup$
1
  • $\begingroup$ (to the uninitiated: the strings in this language have two equal halves, where both halves are matched parentheses, or neither is. The communication consists of one bit which specifies whether your half is matched parentheses) $\endgroup$
    – user253751
    Oct 9 '20 at 12:14
1
$\begingroup$

Let $L'$ be an arbitrary language, and consider $$ L = \{ \Sigma^{|x|} x : x \in L' \}. $$ Then $L$ has roughly the same complexity as $L'$, but it has communication complexity $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.