has abstract
| - 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". (en)
- A medida de recurso delimitado de Lutz é uma generalização da Medida de Lebesgue para classes de complexidade. Foi originalmente desenvolvida por . Assim como a medida de Lebesgue dá um método para quantificar o tamanho de subconjuntos do Espaço euclideano , a medida de recurso delimitado dá um método para classificar o tamanho de subconjuntos de classes de complexidade. Por exemplo, os cientistas da computação em geral acreditam que a classe de complexidade P (o conjunto de todos os problemas de decisão solúveis em tempo polinomial) não é igual à classe de complexidade NP (o conjunto de todos os problemas de decisão verificável, mas não necessariamente solucionável, em tempo polinomial). Uma vez que P é um subconjunto de NP, isso significaria que NP contém mais problemas do que P. Uma hipótese mais forte que indica que "P é diferente de NP" é a afirmação "NP não tem p-medida 0". Aqui, p-medida é uma generalização da medida de Lebesgue para os subgrupos da classe de complexidade E, em que P é contida. P é conhecida por ter p-medida de 0, e assim a hipótese de "NP não tem p-medida 0" implica não somente que NP e P são desiguais, mas que NP é, em sentido de medida teórica, "muito maior que P". (pt)
|