0
$\begingroup$

Given two unrelated languages $L_0$ and $L_1$ contained in some complexity class $C$. Is the language $L_x=L_0\times L_1= \{(x,y)|x\in L_0, y\in L_1\}$ always contained in $C$?

And if that is the case, can we just extend this recursively and create a single language $(L_{All})$ from all other languages contained in $C$ (even if the count of languages in $C$ is infinite)? Is the language $L_{All}$ always contained in $C$ as well?

$\endgroup$
4
  • 1
    $\begingroup$ You will have to explain what "extending this recursively" would mean - how would you extend recursively? Do you start from two languages $L_0,L_1$ and construct $L_2:=L_0\times L_1$, and then $L_3:=L_1\times L_2$, and so on with the recurrence formula of $L_{n+2}=L_n\times L_{n+1}$ ? Is this the process you have in your mind? $\endgroup$
    – nir shahar
    Jan 4 at 16:38
  • $\begingroup$ The answer depends on the class $C$. $\endgroup$ Jan 4 at 16:43
  • $\begingroup$ @nirshahar yes. Exactly. $\endgroup$
    – J.Doe
    Jan 4 at 17:34
  • $\begingroup$ @YuvalFilmus i understand/agree. I was reffering to the english meaning. I guess I should have used 'arbitrary' or something similar. $\endgroup$
    – J.Doe
    Jan 4 at 17:36
1
$\begingroup$

The answer depends on the class $C$. Many classes will be closed under your operation, but some are not. For example, DCFL, the class of all deterministic context-free language, is not. To show this, we slightly adapt the counterexample in this answer. Define $$ L_A = \{ a^i b^j c^k : i \neq j \}; L_B = \{ a^i b^j c^k : j \neq k \}; L_1 = \{ ,w : w \in L_A \} \cup L_B; L_0 = \; ,^* $$ The languages $L_0$ and $L_1$ are both DCFL. Let $L_x = L_0 \times L_1$ be their product. Suppose that $L_x$ were DCFL. Then so would $L_y = \{ w : (w) \in L_x \}$ be, since DCFL is closed under quotient. Since DCFL is closed under intersection with a regular language, $L_z = L_y \cap \, ,,(a+b+c)^*$ would be DCFL. Notice that $L_z = \, ,, (L_A \cup L_B)$. Again using closure under quotient, it would follow that $L_A \cup L_B$ is DCFL, but that is known to be false.

$\endgroup$
4
  • $\begingroup$ Thanks a lot. I am still trying to understand the counterexample. Assuming the class $C$ is the class i.e. $\Sigma_2^P$ in the second level of the polynomial hierarchy. Is that one closed under the above criteria? $\endgroup$
    – J.Doe
    Jan 4 at 17:40
  • 1
    $\begingroup$ You can ask as many questions as there are complexity classes. Some complexity classes are closed, since aren’t. There’s no general rule. $\endgroup$ Jan 4 at 17:40
  • $\begingroup$ I understand. But for the specific case of $\Sigma_2^P$ any pointers how to figure it out? $\endgroup$
    – J.Doe
    Jan 4 at 17:47
  • $\begingroup$ Use the definition. $\endgroup$ Jan 4 at 17:48

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.