Can we use exponential function in a reduction?

Question

If I have an NP-complete graph problem $P1$ whose instance, say, a graph $G$ and a positive integer $k$ and I have another graph problem $P2$ whose instance is a graph $G'$ and a positive integer $k'$. I would like to prove that $P2$ is NP-complete. The reduction is as follows:

• set $G'= G$ and
• set $k'= f(k)$.
• $P1$ is solved iff $P2$ is solved.

My question is: is this reduction correct when $f(k)$ is exponential function?, For simplicity, say, $f(k)=2^k$. I am afraid that this is no longer polynomial-time but then again calculating $2^k$ or $k!$ is polynomial-time problem.

My whole question is general as the title mentions: Can we use exponential function in a reduction to create some parameter in the instance of the concerned problem?

EDIT

My question is motivated by the validity of using exponentiation in polytime reduction on cstheory.SE where the OP asks about a specific reduction used in some paper. My question is general about using exponentiation in reduction.

Answer 1

For the sake of notation, I'm going to assume you're trying to produce a polynomial time reduction $f$, which that maps instances $x$ of some problem $L_1$ to instances $f(x)$ of some other problem $L_2$. Instances of $L_i$ have parameter $p_i$ ($i\in\{1,2\}$). Since the reduction has to run in polynomial time, it has to output at most a polynomial number of bits, say $|x|^q$ for some constant $q$. In particular, the representation of $p_2$ can't be more than $|x|^q$ bits long.

So, suppose the value of the parameter is $k$ in some instance $x$ with parameter $p_1=k$. Whether or not $f(x)$ can have parameter $p_2=2^k$ depends entirely on what the parameters are and how big $p_1$ can be.

If $p_1$ is a number represented in unary, we have $p_1\leq |x|$; if it's a number represented in binary or some higher base, then $p_1 = O(2^{|x|})$. If $p_1$ is the size of some object described in $x$, then its size will depend on what kind of object it is (e.g., if $p_1$ is the size of some set of a graph's the vertices, $p_1\leq |x|$; if it's the number of pairs of vertices with some property, $p_1\leq |x|^2$, and so on).

And, now, what's $p_2$? If it's a number in unary, then $2^k$ is a string of length $2^k$, so we need $2^k\leq |x|^q$, i.e., $k=O(\log |x|)$. If it's a number in binary, then $2^k$ is just a $1$ followed by $k$ zeroes, so we can write this in our output as long as $k=O(|x|^q)$. If it's the size of some structure then, again, it depends on how that structure is represented. For example, if you need to add $2^k$ vertices, you need all those vertices to be stored in at most $|x|^q$ characters, so $k$ had better not be any bigger than about $\log n$.