2
$\begingroup$

As I understand, the term "NP-hardness" is applicable when we also talk about optimization or search problems (i.e. return the satisfying assignment for 3-SAT). How do we formally define NP-hardness for such problems? The standard definition:

The problem is NP-hard when any problem from NP is polynomial-time reducible to this problem

doesn't make much sense, because of how the reduction is defined:

Language $A$ is polynomial-time reducible to $B$ if there exists a poly-time computable function $f$, such that $x \in A$ iff $f(x) \in B$.

The problem is that $B$ (e.g. our search problem) doesn't define a language (there may be other equivalent definitions, such as $A(x) \in \{true, false\}$, but they'll lead to the same problems).

My friend suggested that we can define a second poly-time computable function $g^{-1}$, which converts an "answer" for $B$ to answer for $A$: $x \in A$ iff $g^{-1}(B(f(x)))$ is $true$, where $B(y)$ is any correct answer for $y$. This makes sense, but I've never seen that.

So, what's the standard definition? For an answer, I would also ask for an appropriate citation (not to Wikipedia or random slides).

$\endgroup$
  • $\begingroup$ Have you read the Wikipedia article discussing it? NP-optimization problem (NPO) $\endgroup$ – Pål GD Aug 24 at 8:22
  • $\begingroup$ @PålGD, I've read it, but I'm not sure how it answers my question. $\endgroup$ – Dmitry Aug 24 at 8:55
5
$\begingroup$

There is a slight abuse of notation going on. We say that a function $f$ is NP-hard if $f\in FP$ implies $P=NP$. For example, if $L$ is NP complete and $M_L(x,y)$ is a verifier for $L$, then any function $f$ which maps $x$ to some $y$ such that $M_L(x,y)$ whenever such $y$ exists is of course NP-hard in this sense. We don't usually talk about actual reductions in this context, however the natural way to go about saying $L$ reduces to computing $f$ is to say that there exists a polynomial time oracle machine $M^f$ with access to $f$ that decides $L$.

See also the zoo on the class FNP. The fact that "function NP" problems are defined relative to a specific verifier introduces some difficulty when talking about search to decision reduction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a strange definition. Since we believe that $P \ne NP$, $(f \in FP \Rightarrow P=NP) = (f \not \in FP \lor P=NP) = f \not \in FP$, so $NP$-hard $= \overline{FP}$? And isn't "exists a polynomial time oracle machine $M^f$" a stronger type of reduction than we want (we want only a single oracle execution)? $\endgroup$ – Dmitry Aug 24 at 9:11
  • $\begingroup$ Function classes are more general than languages, you can't compare them directly. If $\mathcal{F}\subseteq\{0,1\}^{\{0,1\}^*}$ is a class of functions then $NP, \mathcal{F}$ are obviously different, they just don't contain the same objects, so your conclusion is false for trivial reasons. This notion of reduction allows us to bypass the need for a new definition of reductions for relations in FNP. If it helps, this notation is also used for approximations, e.g. saying "f is NP-hard to approximate" is a shorthand for "an approximation for f yields a polynomial algorithm for SAT". $\endgroup$ – Ariel Aug 24 at 9:31
  • $\begingroup$ "Forcing" the reduction structure from decision problems on search problems doesn't work. For example, if we define (as you suggested) $A$ reduces to $f$ iff there exists polynomial $B$ s.t. $B(f(x))\iff x\in A$ for all $x$, then we run into problems if $f$ is not injective. $\endgroup$ – Ariel Aug 24 at 9:50
2
$\begingroup$

You will not find a reference for "the standard definition" of NP-hardness. Some authors restrict the notion "NP-hard" to decision problems only, and use the definition of reduction you mention in your question (which is sometimes referred to as a "Karp reduction" or "many-one reduction"). Other authors use the term more loosely, and extend the notion to other types of problem (such as search or optimization problems). You can find a bit of historical background in Donald Knuth's "Postscript about NP-hard problems".

The wikipedia article explicitly discusses this (and gives some references):

A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H. [...]

Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H. [...] Awkwardly, it does not restrict the class NP-hard to decision problems, and it also includes search problems or optimization problems.

The suggestion of your friend has some similarities with Cook reductions, which are sometimes used as the more loose definition of "NP-hardness". The suggestion of your friend captures well what people usually mean when they talk about an optimization problem being NP-hard.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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