<p>Suppose that for every <span class="math-container">$k \in \mathbb{N}$</span> the decision problem <span class="math-container">$A_k$</span> is hard for <span class="math-container">$\mathsf{N}k\text{-}\mathsf{ExpTime}$</span>.</p>
<p>What is the complexity of their disjoint union <span class="math-container">$A = \{ (k,x) \mid k\in \mathbb{N}, x\in A_k \}$</span>?<br />
It is in the fourth level of the <a href="https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy" rel="nofollow noreferrer">Grzegorczyk hierarchy</a> <span class="math-container">$\mathcal{E}^4$</span> and
is hard for <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#elementary" rel="nofollow noreferrer"><span class="math-container">$\mathsf{Elementary}$</span></a>.
But can we say more?</p>
<h3>Motivation</h3>
<p>I am studying the complexity of the satisfiability of monadic logics
with several equivalence symbols in agreement.
Let <span class="math-container">$k$</span> be the number of equivalence symbols allowed.
If <span class="math-container">$k$</span> is fixed then problem is complete for <span class="math-container">$\mathsf{N}k\text{−}\mathsf{ExpTime}$</span>.</p>
<p>I am looking for a nice characterization of the complexity of the problem
when <span class="math-container">$k$</span> is not a fixed parameter but part of the input.</p>

CC BY-SA 3.0
2016-05-10T22:29:04.810Z
I don't have a strong enough intuition about complexity classes. This is not an exercise, it is something I thought was obvious but i don't trust myself on complexity classes questions. I'm studying the complexity of the satisfiability of monadic logics with several equivalence symbols in agreement (whatever that means), and it turns out that if the number of equivalence symbols allowed is a fixed $k$, then the corresponding problem is $\mathsf{N}k-\mathsf{ExpTime}$-complete. So your comment is enough for me!
comco
CC BY-SA 3.0
2016-05-10T23:03:00.327Z
Even if you drop the nondeterminism  and use $A_k$s 
which are hard for $k\text{-}\mathsf{ExpTime}$
their disjoint union $A$ 
will be hard for $k\text{-}\mathsf{ExpTime}$ for every $k$.
Therefore it is hard for their union which is equal to Elementary. If a problem is hard for a family of classes it is hard for their union as well.
Kaveh
CC BY-SA 3.0
2016-05-11T18:15:24.007Z
I think their disjoint union is complete for the fourth level. IIRC, the fourth level is essentially obtained by a diagonal function for Elementary and that is reducible to $A$.
Kaveh
CC BY-SA 3.0
2016-05-11T18:36:52.783Z
@Kaveh The time hierarchy theorem ensures that just like the third level, the fourth level has no complete problem at all. The argument you have in mind wouldn't work anyway without some uniformity condition, as each $k$ can in principle use a completely different reduction.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><computability>
The complexity of the disjoint union of a sequence of complete problems
comco
# The complexity of the disjoint union of a sequence of complete problems

(Asked by: username_0 on 2016-05-10)

Suppose that for every $k \in \mathbb{N}$ the decision problem $A\_k$ is hard for $\mathsf{N}k\text{-}\mathsf{ExpTime}$.

What is the complexity of their disjoint union $A = \{ (k,x) \mid k\in \mathbb{N}, x\in A\_k \}$?  
It is in the fourth level of the [Grzegorczyk hierarchy](https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy) $\mathcal{E}^4$ and
is hard for [$\mathsf{Elementary}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#elementary).
But can we say more?

### Motivation

I am studying the complexity of the satisfiability of monadic logics
with several equivalence symbols in agreement.
Let $k$ be the number of equivalence symbols allowed.
If $k$ is fixed then problem is complete for $\mathsf{N}k\text{−}\mathsf{ExpTime}$.

I am looking for a nice characterization of the complexity of the problem
when $k$ is not a fixed parameter but part of the input.

**Tags:** cc.complexity-theory, complexity-classes, computability
> **Comments:**
> **username_0**: I don't have a strong enough intuition about complexity classes. This is not an exercise, it is something I thought was obvious but i don't trust myself on complexity classes questions. I'm studying the complexity of the satisfiability of monadic logics with several equivalence symbols in agreement (whatever that means), and it turns out that if the number of equivalence symbols allowed is a fixed $k$, then the corresponding problem is $\mathsf{N}k-\mathsf{ExpTime}$-complete. So your comment is enough for me!  
> **username_1**: Even if you drop the nondeterminism  and use $A_k$s  which are hard for $k\text{-}\mathsf{ExpTime}$ their disjoint union $A$  will be hard for $k\text{-}\mathsf{ExpTime}$ for every $k$. Therefore it is hard for their union which is equal to Elementary. If a problem is hard for a family of classes it is hard for their union as well.  
> **username_1**: I think their disjoint union is complete for the fourth level. IIRC, the fourth level is essentially obtained by a diagonal function for Elementary and that is reducible to $A$.  
> **username_2**: @Kaveh The time hierarchy theorem ensures that just like the third level, the fourth level has no complete problem at all. The argument you have in mind wouldn't work anyway without some uniformity condition, as each $k$ can in principle use a completely different reduction.  

---

## 0 answers

