Altered title. Add: arxiv, doi-access, authors 1-1. Removed URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Ira Leviton | Category:CS1 maint: unflagged free DOI | #UCB_Category 4/37
Time-bounded Kolmogorov complexity is a modified version of Kolmogorov complexity where the space of programs to be searched for a solution is confined to only programs that can run within some pre-defined number of steps.<ref>{{Cite journal |lastlast1=Hirahara |firstfirst1=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|doi-access=free }}</ref> It is hypothesised that the possibility of the existence of an efficient algorithm for determining approximate time-bounded Kolmogorov complexity is related to the question of whether true [[one-way function]]s exist.<ref>{{Cite web |last=Klarreich |first=Erica |date=2022-04-06 |title=Researchers Identify ‘Master'Master Problem’Problem' Underlying All Cryptography |url=https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ |access-date=2024-11-16 |website=Quanta Magazine |language=en}}</ref><ref>{{Citation |lastlast1=Liu |firstfirst1=Yanyi |title=On One-way Functions and Kolmogorov Complexity |date=2020-09-24 |url=https://arxiv.org/abs/2009.11514 |access-date=2024-11-16 |doiarxiv=10.48550/arXiv.2009.11514 |last2=Pass |first2=Rafael}}</ref>
