Resource Bounded Measure
Lutz's resource bounded measure is a generalisation of Lebesgue measure to complexity classes. It was originally developed by Jack Lutz. Just as Lebesgue measure gives a method to quantify the size of subsets of the Euclidean space, resource bounded measure gives a method to classify the size of subsets of complexity classes.
For instance, computer scientists generally believe that the complexity class P (the set of all decision problems solvable in polynomial time) is not equal to the complexity class NP (the set of all decision problems checkable, but not necessarily solvable, in polynomial time). Since P is a subset of NP, this would mean that NP contains more problems than P. A stronger hypothesis than "P is not NP" is the statement "NP does not have p-measure 0". Here, p-measure is a generalization of Lebesgue measure to subsets of the complexity class E, in which P is contained. P is known to have p-measure 0, and so the hypothesis "NP does not have p-measure 0" would imply not only that NP and P are unequal, but that NP is, in a measure-theoretic sense, "much bigger than P".
Read more about Resource Bounded Measure: Definition, Almost Complete
Famous quotes containing the words resource, bounded and/or measure:
“Your kind doesn’t just kill men. You murder their spirits, you strangle their last breath of hope and freedom, so that you, the chosen few, can rule your slaves in ease and luxury. You’re a sadist just like the others, Heiser, with no resource but violence and no feeling but fear, the kind you’re feeling now. You’re drowning, Heiser, drowning in the ocean of blood around this barren little island you call the New Order.”
—Curtis Siodmak (1902–1988)
“I could be bounded in a nutshell and count myself a king of
infinite space, were it not that I have bad dreams.”
—William Shakespeare (1564–1616)
“Nobody is glad in the gladness of another, and our system is one of war, of an injurious superiority. Every child of the Saxon race is educated to wish to be first. It is our system; and a man comes to measure his greatness by the regrets, envies, and hatreds of his competitors.”
—Ralph Waldo Emerson (1803–1882)