3
$\begingroup$

So, I've just begun dabbling in complexity theory and I'm somewhat confused as to the relationship between NP-hardness and function computation. As far as I've understood, NP-hardness is defined for decision and search problem but I've also seen mention of functions whose values are considered NP-hard to compute.

My question is, then, are there functions $f: \mathbb{N} \rightarrow \mathbb{N}$ whose values are NP-hard to calculate? If not, what is the appropriate notion of hardness for calculating the value of a function?

$\endgroup$
3
$\begingroup$

Yes. For instance, define $f$ so that $f(x)=1$ if $x$ is an encoding of a 3-colorable graph, or $f(x)=0$ otherwise. Since 3-coloring is NP-hard, it is NP-hard to compute $f$. (If you could compute $f$ efficiently, you could solve 3-coloring efficiently.)

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