<p>The latter. The former is impossible for NP-complete languages by the nondeterministic time hierarchy theorem: assume for contradiction that <span class="math-container">$B$</span> is a language computable in nondeterministic time <span class="math-container">$p(n)$</span> such that every NP language reduces to it in time <span class="math-container">$q(n)$</span>. Then
<span class="math-container">$$\mathrm{NP}\subseteq\mathrm{NTIME}(q(n)+p(q(n)))
\subsetneq\mathrm{NTIME}((q(n)+p(q(n)))n)\subseteq\mathrm{NP},$$</span>
a contradiction.</p>

<p>You asked more generally about NP-<em>hard</em> languages. Consider the language <span class="math-container">$B\in\mathrm{NEXP}$</span> defined as
<span class="math-container">$$B=\{M\#w:\text{$M$ is a clocked poly-time NTM and $M$ accepts $w$}\}.$$</span>
It is clear that any NP-language <span class="math-container">$A$</span> reduces to <span class="math-container">$B$</span> in time <span class="math-container">$n+c_A$</span> for some constant <span class="math-container">$c_A$</span>, namely <span class="math-container">$c_A=1+|M_A|$</span> where <span class="math-container">$M_A$</span> is a fixed NTM accepting <span class="math-container">$A$</span>.</p>

<p>But in fact, every <span class="math-container">$A\in\mathrm{NP}$</span> reduces to <span class="math-container">$B$</span> in time <span class="math-container">$3n+c$</span> for some constant <span class="math-container">$c$</span> independent of <span class="math-container">$A$</span>. The reduction function reads up to the first <span class="math-container">$c_A$</span> letters of the input, storing them in its state. If the input has length <span class="math-container">$\le c_A$</span>, the reduction directly finds the result in a lookup table, and outputs one of two fixed inputs that make <span class="math-container">$B$</span> accept or reject as appropriate. Otherwise, it outputs the description of <span class="math-container">$M_A$</span>, copies the first <span class="math-container">$c_A$</span> 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
<span class="math-container">$$\begin{cases}n+c,&amp;n\le c_A,\\c_A+2c_A+(n-c_A)\le3n,&amp;n&gt;c_A\end{cases}$$</span>
for some absolute constant <span class="math-container">$c$</span> independent of <span class="math-container">$A$</span>.</p>

CC BY-SA 4.0
2020-03-09T16:30:56.913Z
For the second part, I’m assuming that the input alphabet of all the languages is fixed.
Emil Jeřábek
CC BY-SA 4.0
2020-03-09T07:49:44.660Z
2020-03-09T16:22:15.250Z
2020-03-09T16:22:15.250Z
Emil Jeřábek
<p>It is the latter, i.e. there is a polynomial <span class="math-container">$q_L$</span> for every language <span class="math-container">$L$</span>. A clear way to see this is in the proof of the Cook-Levin Theorem. </p>

<p>The theorem requires the construction of a polynomial size-bounded tableau depending on the time bound for a NTM deciding <span class="math-container">$L$</span>. 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 <span class="math-container">$L$</span>, which can be a different polynomial in the reduction to SAT. </p>

CC BY-SA 4.0
2020-03-09T05:00:12.160Z
2020-03-09T05:00:12.160Z
nathan34
<p>Arora and Barak define NP-completeness as the following:</p>

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

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

<cc.complexity-theory><np-hardness><complexity-classes>
Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials?
Hans Schmuber
# Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials?

(Asked by: username_0 on 2020-03-08)

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.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes

---

## 2 answers

### Answer by username_1 on 2020-03-09. Score: 3 | Accepted answer

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

> **Comments:**
> **username_1**: For the second part, I’m assuming that the input alphabet of all the languages is fixed.  

---

### Answer by username_2 on 2020-03-09. Score: 1

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.


---

