1
$\begingroup$

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.)

$\endgroup$

closed as unclear what you're asking by David Richerby, Luke Mathieson, Juho, Ran G., Gilles Jun 7 '15 at 16:54

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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. $\endgroup$ – David Richerby Jun 2 '15 at 22:32
  • $\begingroup$ Are you referring to padding? $\endgroup$ – Yuval Filmus Jun 3 '15 at 5:03
  • 1
    $\begingroup$ What does parameter mean in this context? You may be interested in succinctly represented problems. $\endgroup$ – Tom van der Zanden Jun 3 '15 at 7:34
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.