Content deleted Content added
Citation bot (talk | contribs) 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 |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed access-date with no URL. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Algorithmic information theory | #UCB_Category 17/22 |
||
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 is confined to only programs that can run within some pre-defined number of steps.<ref>{{Cite journal |last1=Hirahara |first1=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 |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 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 |last1=Liu |first1=Yanyi |title=On One-way Functions and Kolmogorov Complexity |date=2020-09-24
==See also==
| |||