Definition
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
We write
Let S be a subset of P(N) and ≤ a reduction, then S is called closed under ≤ if
A subset A of N is called hard for S if
A subset A of N is called complete for S if A is hard for S and A is in S.
Read more about this topic: Reduction (complexity)
Famous quotes containing the word definition:
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)