Content deleted Content added
→Time-bounded complexity: the pre-print in question - yes, it's a pre-print, but this is cryptology, and the mainstream media coverage justifies linking it here |
m Duplicate word reworded |
||
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 |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> It is hypothesised that the possibility of the existence of an efficient algorithm for determining approximate time-bounded Kolmogorov complexity is related to
==See also==
| |||