0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For the second part, I’m assuming that the input alphabet of all the languages is fixed. $\endgroup$ – Emil Jeřábek Mar 9 at 16:30
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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