# Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]

Arora and Barak define NP-completeness as the following:

"We say that a language $$A \subseteq \{0, 1\}^∗$$ is polynomial-time Karp reducible to a language $$B \subseteq \{0, 1\}^∗$$ denoted by $$A \leq_p B$$ if there is a polynomial-time computable function $$f : \{0, 1\}^∗ \rightarrow \{0, 1\}^*$$ such that for every $$x \in \{0, 1\}^∗$$, $$x \in A$$ if and only if $$f(x) \in B$$. We say that B is NP-hard if A $$\leq_p$$ B for every $$A \in NP$$. We say that B is NP-complete if B is NP-hard and $$B \in NP$$."

However, something about this is not clear to me: if B is NP-hard, does that mean for all languages $$L\in NP$$, there is a single fixed polynomial $$q$$ such that the associated function $$f$$ is computable in time $$q(n)$$? Or does it mean for each language $$L\in NP$$, the function $$f$$ is computable in time $$q_L$$, where $$q_L$$ is a polynomial depending on the language. These polynomials $$q_L$$ can be arbitrarily large.

The latter. The former is impossible for NP-complete languages by the nondeterministic time hierarchy theorem: assume for contradiction that $$B$$ is a language computable in nondeterministic time $$p(n)$$ such that every NP language reduces to it in time $$q(n)$$. Then $$\mathrm{NP}\subseteq\mathrm{NTIME}(q(n)+p(q(n))) \subsetneq\mathrm{NTIME}((q(n)+p(q(n)))n)\subseteq\mathrm{NP},$$ a contradiction.
You asked more generally about NP-hard languages. Consider the language $$B\in\mathrm{NEXP}$$ defined as $$B=\{M\#w:\text{M is a clocked poly-time NTM and M accepts w}\}.$$ It is clear that any NP-language $$A$$ reduces to $$B$$ in time $$n+c_A$$ for some constant $$c_A$$, namely $$c_A=1+|M_A|$$ where $$M_A$$ is a fixed NTM accepting $$A$$.
But in fact, every $$A\in\mathrm{NP}$$ reduces to $$B$$ in time $$3n+c$$ for some constant $$c$$ independent of $$A$$. The reduction function reads up to the first $$c_A$$ letters of the input, storing them in its state. If the input has length $$\le c_A$$, the reduction directly finds the result in a lookup table, and outputs one of two fixed inputs that make $$B$$ accept or reject as appropriate. Otherwise, it outputs the description of $$M_A$$, copies the first $$c_A$$ input letters from the internal state to the output, and proceeds to copy the rest of the input. The running time is thus bounded by $$\begin{cases}n+c,&n\le c_A,\\c_A+2c_A+(n-c_A)\le3n,&n>c_A\end{cases}$$ for some absolute constant $$c$$ independent of $$A$$.
It is the latter, i.e. there is a polynomial $$q_L$$ for every language $$L$$. A clear way to see this is in the proof of the Cook-Levin Theorem.
The theorem requires the construction of a polynomial size-bounded tableau depending on the time bound for a NTM deciding $$L$$. The time bound changes depending on the language, of course. So the tableau used in the reduction has a size dependent on the NTM deciding $$L$$, which can be a different polynomial in the reduction to SAT.