scientific article; zbMATH DE number 2081089
From MaRDI portal
Publication:4474202
zbMath1052.68059MaRDI QIDQ4474202
Publication date: 4 August 2004
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2245/22450001.htm
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Nonuniform reductions and NP-completeness ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ A circuit complexity formulation of algorithmic information theory ⋮ Avoiding simplicity is complex ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ Dimension, entropy rates, and compression ⋮ A note on dimensions of polynomial size circuits ⋮ Natural Proofs versus Derandomization ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Hardness magnification near state-of-the-art lower bounds
This page was built for publication:
