Axiomatizing Resource Bounds for Measure

DOI10.1007/978-3-642-21875-0_11zbMath1344.68086arXiv1102.2095OpenAlexW1829057729MaRDI QIDQ3091445

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

Publication date: 9 September 2011

Published in: Models of Computation in Context (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.2095

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other connections with logic and set theory (28E15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An outer-measure approach for resource-bounded measure
• Martingale families and dimension in P
• Resource-bounded measure on probabilistic classes
• Almost everywhere high nonuniform complexity
• Polynomial and abstract subrecursive classes
• Measure on \(P\): Strength of the notion
• Logics for reasoning about cryptographic constructions
• On characterizations of the basic feasible functionals, Part I
• Dimension, Halfspaces, and the Density of Hard Sets
• Measure, Stochasticity, and the Density of Hard Languages
• A new Characterization of Type-2 Feasibility
• Adventures in time and space
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage

This page was built for publication: Axiomatizing Resource Bounds for Measure