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.)
Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete?
complexity theory;time complexity
I am not 100% sure that I understand the question but here is an attempt where I reformulate your problem.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$).