A stronger Kolmogorov zero-one law for resource-bounded measure

DOI10.1016/S0304-3975(02)00320-1MaRDI QIDQ1870565zbMATH OpenFDO

Authors Jack Jie Dai

Publication date 14 May 2003

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

zbMATH Keywords

computational complexitymartingaleresource-bounded measureKolmogorov zero-one law

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1335897
• scientific article; zbMATH DE number 1346358
• Resource-bounded measure on probabilistic classes
• Compressibility and resource bounded measure
• Compressibility and resource bounded measure

Cites work

• scientific article; zbMATH DE number 1335897 (Why is no real title available?)
• scientific article; zbMATH DE number 1048036 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• scientific article; zbMATH DE number 3008903 (Why is no real title available?)
• scientific article; zbMATH DE number 3034029 (Why is no real title available?)
• A unified approach to the definition of random sequences
• Almost everywhere high nonuniform complexity
• Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
• Process complexity and effective random tests

Cited in

(5)

• An upward measure separation theorem
• Axiomatizing resource bounds for measure
• Resource-bounded measure on probabilistic classes
• A variation on the zero-one law
• An outer-measure approach for resource-bounded measure

This page was built for publication: A stronger Kolmogorov zero-one law for resource-bounded measure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1870565)