scientific article; zbMATH DE number 2196513

MaRDI QIDQ5465360zbMATH OpenFDO

Authors Lance Fortnow

Publication date 22 August 2005

zbMATH Keywords

complexity classesP-printable setsP/poly

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 107775
• scientific article; zbMATH DE number 107774
• Around Kolmogorov complexity: basic notions and results
• scientific article; zbMATH DE number 7701424
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

Cited in

(21)

• Kolmogorov complexity arguments in combinatorics
• NL-printable sets and nondeterministic Kolmogorov complexity
• Kolmogorov complexity
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• scientific article; zbMATH DE number 5294121 (Why is no real title available?)
• Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity
• scientific article; zbMATH DE number 3982519 (Why is no real title available?)
• scientific article; zbMATH DE number 1343489 (Why is no real title available?)
• Kolmogorov Complexity Theory over the Reals
• Kolmogorov Complexity: Sources, Theory and Applications
• Weihrauch Complexity in Computable Analysis
• Randomness and intractability in Kolmogorov complexity
• STACS 2005
• Kolmogorov's contributions to information theory and algorithmic complexity
• Kolmogorov complexity conditional to large integers
• Logical operations and Kolmogorov complexity
• Kolmogorov complexity and non-determinism
• scientific article; zbMATH DE number 7701424 (Why is no real title available?)
• Algebraic barriers to halving algorithmic information quantities in correlated strings
• An efficient coding theorem via probabilistic representations and its applications
• Algebraic barriers to halving algorithmic information quantities in correlated strings

This page was built for publication:

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