3
$\begingroup$

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 $\mathcal{E}^4$ and is hard for $\mathsf{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.

$\endgroup$
  • 2
    $\begingroup$ 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! $\endgroup$ – comco May 10 '16 at 22:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh May 10 '16 at 23:03
  • $\begingroup$ 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$. $\endgroup$ – Kaveh May 11 '16 at 18:15
  • 2
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek May 11 '16 at 18:36

Your Answer

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

Browse other questions tagged or ask your own question.