Revision as of 09:54, 16 November 2024 edit The Anome (talk \| contribs) Edit filter managers, Administrators 260,106 edits →Conditional versions: == Time-bounded complexity ==, because that's not in the same class as the others Tag: 2017 wikitext editor ← Previous edit		Revision as of 10:03, 16 November 2024 edit undo The Anome (talk \| contribs) Edit filter managers, Administrators 260,106 edits →Time-bounded complexity: more Tag: Visual edit Next edit →
Line 390: == Time-bounded complexity == Time-bounded Kolmogorov complexity is a modified version of Kolmogorov complexity where the space of programs to be searched for a solution ~~are~~is confined to only programs that can run within asome pre-defined number of steps.<ref>{{Cite journal \|last=Hirahara \|first=Shuichi \|last2=Kabanets \|first2=Valentine \|last3=Lu \|first3=Zhenjian \|last4=Oliveira \|first4=Igor C. \|date=2024 \|title=Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity \|url=https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.29 \|journal=39th Computational Complexity Conference (CCC 2024) \|language=en \|publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik \|pages=29:1–29:56 \|doi=10.4230/LIPIcs.CCC.2024.29}}</ref> ==See also==

Kolmogorov complexity: Difference between revisions