About: Resource bounded measure     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FResource_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.

AttributesValues
rdfs:label
  • Resource bounded measure (en)
  • Medida de recurso delimitado (pt)
rdfs:comment
  • 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. (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. (pt)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
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)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 42 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software