HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can it be NP hard to calculate the value of a function?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canthehardfunctionvaluecalculate

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#148378, answer score: 3

Revisions (0)

No revisions yet.