5
$\begingroup$

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}$?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ In my experience, it often helps to check the definitions in a textbook. Wikipedia is often hopeless with TCS content. $\endgroup$
    – Raphael
    Commented Oct 3, 2012 at 15:33
  • $\begingroup$ What books do you recommend? $\endgroup$
    – Tim
    Commented Oct 3, 2012 at 15:37
  • $\begingroup$ @Tim There's a nice preprint available online: cs.berkeley.edu/~vazirani/algorithms.html If you're going to be studying computer science, it's a nice one to own. $\endgroup$
    – Joe
    Commented Oct 3, 2012 at 18:20
  • $\begingroup$ Chapter 8 of Algorithm Design by Kleinberg and Tardos is also good. I consider that one worth owning as well if you're going to be spending a lot of time in theoretical computer science. The solved exercises are excellent for learning. $\endgroup$
    – Joe
    Commented Oct 3, 2012 at 18:27
  • $\begingroup$ CLRS is the standard reference. It has probably covers the most material of any algorithms book, but it's not quite as accessible. amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/… $\endgroup$
    – Joe
    Commented Oct 3, 2012 at 18:29

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks! (1) when you wrote $x\in B$, do you treat $B$ as the set of solutions for problem B, and $x$ is one of the solution? (2) "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." Do you mean a problem corresponds to a subset of $\mathbb{N}$ or of $\Sigma^*$ for some alphabet $\Sigma$, by the subset being a set of inputs for which the problem has answer YES? $\endgroup$
    – Tim
    Commented Oct 3, 2012 at 14:19
  • $\begingroup$ (3) Do "a solution to a problem" and "an input for which the problem has answer YES" mean the same? (4) Are the problems in discussion some special kind of problems? $\endgroup$
    – Tim
    Commented Oct 3, 2012 at 14:25
  • $\begingroup$ (4) Does $x \in B$ iff $f(x) \in A$ mean the same as $f(B)=A$? Is $f$ not necessarily injective? $\endgroup$
    – Tim
    Commented Oct 3, 2012 at 14:36
  • $\begingroup$ @Tim The syntax is similar to that used for languages. Here $x$ is an input, $B$ is "a decision problem" or "the set of inputs for which a correct algorithm for the decision problem outputs yes". $\endgroup$
    – Joe
    Commented Oct 3, 2012 at 18:20
  • $\begingroup$ @Tim (1) We think of each "problem" as a property of the input. The set corresponding to the problem consists of these inputs for which the property holds. (2) $\mathbb{N}$ can be identified as the set of finite strings over some finite alphabet $\Sigma$. For example, for $\Sigma=\{0,1\}$ you can take the encoding which drops the MSB of the binary encoding of the number. So $5$ would code 01 and $13$ would code 101. (3) A solution to a problem, in this context, is an algorithm for it, which decides whether the input satisfies the property given by the problem. [cont.] $\endgroup$
    – Yuval Filmus
    Commented Oct 3, 2012 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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