# Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete? [closed]

Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ EXPTIME or NEXPTIME complete? I.e. If a problem of exponential size relative to a NPC problem is of linear size in another problem, is the other problem exponential time complete? (I think there needs to be an upper bound on the complexity of translating, but I'm not entirely sure what that would be.)

• What does "when translated" mean? Given sufficient computational power, for example, one could translate all "yes" instances of $A$ to some specific "yes" instance of $B$ and all "no" instances to some specific "no" instance of $B$, so $B$ could even be decidable in constant time. – David Richerby Jun 2 '15 at 22:32
• Are you referring to padding? – Yuval Filmus Jun 3 '15 at 5:03
• What does parameter mean in this context? You may be interested in succinctly represented problems. – Tom van der Zanden Jun 3 '15 at 7:34

You have $A,B\subseteq \{0,1\}^*$ and know that $A$ is NP-complete. Furthermore you have a reduction $f$ such that $f(x)\in B$ iff $x\in A$ and such that $|f(x)|$ is in $\log(O(|x|)$. Does that make $B$ NEXPTIME-hard?
Well, since $A$ is NP-complete, I can translate any question $y$ of the the form "does a nondet. TM $M$ halts in time $n$?" into an equivalent question $g(y)$ for $A$, using the reduction that establishes the NP-hardness of $A$. It is thus possible to translate an NEXPTIME-hard question $y$ of the form "does $M$ halts in time $2^n$?" into an equivalent $g'(y)$ for $A$. That reduction is very simple to describe but it produces instances of exponential size. If we could compute $f(g'(x))$ efficiently, we would have a reduction showing that $B$ is NEXPTIME-hard. This is possible in many cases --remember that $g'$ is very simple and that $|f(g'(x))|$ is in $O(|x|)$-- but this depends on knowing $f$ and how nicely it interacts with $g'$.
So I'd say that in general you cannot say that $B$ is NEXPTIME-hard but in many specific cases you'll manage to show it is.
(Final note: the above is about lower bounds. You cannot provide upper bounds for the complexity of $B$ from the assumptions. They only talk about the part of $B$ that is in the image of $f$).