Martingale families and dimension in P

DOI10.1016/J.TCS.2008.02.013zbMath1144.68026OpenAlexW2073125814MaRDI QIDQ930913

Philippe Moser

Publication date: 24 June 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.02.013

zbMATH Keywords

computational complexityeffective dimensionresource-bounded measure

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

A zero-one law for RP and derandomization of AM if NP is not small ⋮ A zero-one SUBEXP-dimension law for BPP ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Nondeterminisic sublinear time has measure 0 in P ⋮ Axiomatizing Resource Bounds for Measure ⋮ An upward measure separation theorem

Cites Work

• Unnamed Item
• Unnamed Item
• The size of SPP
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Resource-bounded measure on probabilistic classes
• Almost everywhere high nonuniform complexity
• Almost every set in exponential time is P-bi-immune
• Measure on \(P\): Strength of the notion
• The zero-one law holds for BPP
• Prediction and dimension
• Finite-state dimension
• The dimensions of individual strings and sequences
• Baire categories on small complexity classes and meager-comeager laws
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Effective fractal dimensions
• Category and Measure in Complexity Classes
• STACS 2004
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Martingale families and dimension in P