Axiomatizing resource bounds for measure

Xiaoyang Gu, Jack H. Lutz, Satyadev Nandakumar, James S. Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the resource bound Δ, which is a class of functions. Most applications of resource-bounded measure use only the "measure-zero/measure-one fragment" of the theory. For this fragment, Δ can be taken to be a class of type-one functions. However, in the full theory of resource-bounded measurability and measure, the resource bound Δ also contains type-two functionals. To date, both the full theory and its zero-one fragment have been developed in terms of a list of example resource bounds. This paper replaces this list-of-examples approach with a careful investigation of the conditions that suffice for a class Δ to be a resource bound.

Original languageEnglish (US)
Title of host publicationModels of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings
Pages102-111
Number of pages10
DOIs
StatePublished - Sep 26 2011
Event7th Conference on Computability in Europe, CiE 2011 - Sofia, Bulgaria
Duration: Jun 27 2011Jul 2 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6735 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Conference on Computability in Europe, CiE 2011
CountryBulgaria
CitySofia
Period6/27/117/2/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Axiomatizing resource bounds for measure'. Together they form a unique fingerprint.

Cite this