[Solved]: Understanding the definition of reduction

ignougroup
Problem Detail: From Wikipedia:

Given two subsets A and B of N and a set of functions F from N to N which is closed under composition, A is called reducible to B under F if $$ exists f in F mbox{ . } forall x in mathbb{N} mbox{ . } x in A Leftrightarrow f(x) in B $$ We write $$ A leq_{F} B $$ Let S be a subset of P(N) and ≤ a reduction, then S is called closed under ≤ if $$ forall s in S mbox{ . } forall A in P(mathbb{N}) mbox{ . } A leq s Rightarrow A in S $$ A subset A of N is called hard for S if $$ forall s in S mbox{ . } s leq A $$ A subset A of N is called complete for S if A is hard for S and A is in S.

I am trying to relate the above definitions to those for problems: problem A can be reduced to problem B, a set of problems are NP-hard, a set of problems are NP-complete. But I don’t know how to relate. I think one link I am missing is to see how a subset of problem can be seen as a subset of $mathbb{N}$?

Asked By : Tim

Answered By : Yuval Filmus

The definition you’re quoting is very abstract, but the concepts you’re trying to understand are pretty intuitive. A problem $A$ is NP-hard if you can solve any problem in NP using it. This means that any $B in NP$ can be reduced to $A$, i.e. there is some polytime function $f$ such that $x in B$ iff $f(x) in A$; so you can test whether $x in B$ by computing $f(x)$ and test whether the latter is in $A$. A problem is NP-complete if it is both in NP-hard and in NP. This means that it is hardest among problems in NP. A problem can be NP-hard without being in NP, for example the halting problem. You’re mentioning sets of problems as belonging to NP, but that’s a typing error: members of NP are problems, in the guise of subsets of the set of natural numbers (or of the set of finite binary strings, which is the same). The subset specifies the set of inputs for which the problem has the answer YES.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4850