1
$\begingroup$

How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?

$\endgroup$
2
$\begingroup$

By definition $EXP = \bigcup_{k\in N}{DTIME\big(2^{n^k}\big)}$.

Let $L_1, L_2 \in EXP$. Then $L_1 \in DTIME\big(2^{n^m}\big)$ and $L_2 \in DTIME\big(2^{n^k}\big)$ for some $k,m \in N$.

So for a string $w$ checking $w \in L_1 \cup L_2$ takes $2^{n^m} + 2^{n^k}$ time which is $O(2^{n^l})$ where $l = max(m,k)$. So $L_1 \cup L_2 \in DTIME\big(2^{n^l}\big)$ and hence in $EXP$.

Let $w$ be a string of length $t$. Then checking $w \in L_1L_2$ takes $t(2^{n^m} + 2^{n^k})$ since for strings $u$ and $v$ such that $w=uv$ we check $w \in L_1$ and $v \in L_2$ $t+1$ times since there are $t$ different prefixes and suffixes of $w$. Assuming $l = max(m,k)$ we have $t2^{n^l}$ running time which is less than $2^t2^{n^l} = 2^{t + n^l}$ which belongs to $EXP$.

Finally, checking $w \in L_1$ takes $O(2^{n^m})$ times so the Turing machine halts with "no" if $w \in L_1$, with "yes" otherwise. Thus $\overline{L}_1^{} \in EXP$.

$\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.