{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:36:59Z","timestamp":1760236619825,"version":"build-2065373602"},"reference-count":7,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T00:00:00Z","timestamp":1638835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1811729"],"award-info":[{"award-number":["CCF 1811729"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. However, is it possible to construct a few strings, no longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that takes as input a string x of length n and returns a list with O(n2) strings, all of length n, such that 99% of them are more complex than x, provided the complexity of x is less than n\u2212loglogn\u2212O(1). We also present an algorithm that obtains a list of quasi-polynomial size in which each element can be produced in polynomial time.<\/jats:p>","DOI":"10.3390\/axioms10040334","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T02:48:13Z","timestamp":1638845293000},"page":"334","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["List Approximation for Increasing Kolmogorov Complexity"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5938-6599","authenticated-orcid":false,"given":"Marius","family":"Zimand","sequence":"first","affiliation":[{"name":"Department of Computer and Information Sciences, Towson University, Baltimore, MD 21252, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,7]]},"reference":[{"key":"ref_1","first-page":"58:1","article-title":"List Approximation for Increasing Kolmogorov Complexity","volume":"Volume 66","author":"Vollmer","year":"2017","journal-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L., Newman, I., and Vereshchagin, N. (2005, January 24\u201326). Increasing Kolmogorov complexity. Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany. Lecture Notes in Computer Science #3404.","key":"ref_2","DOI":"10.1007\/978-3-540-31856-9_34"},{"doi-asserted-by":"crossref","unstructured":"Bauwens, B., Makhlin, A., Vereshchagin, N., and Zimand, M. (2013, January 5\u20137). Short lists with short programs in short time. Proceedings of the 28th IEEE Conference on Computational Complexity, Stanford, CA, USA.","key":"ref_3","DOI":"10.1109\/CCC.2013.19"},{"unstructured":"Bauwens, B., and Zimand, M. (2019). Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time. arXiv.","key":"ref_4"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(76)90005-0","article-title":"Information-Theoretic Characterizations of Recursive Infinite Strings","volume":"2","author":"Chaitin","year":"1976","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Downey, R., and Hirschfeldt, D. (2010). Algorithmic Randomness and Complexity, Springer.","key":"ref_6","DOI":"10.1007\/978-0-387-68441-3"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"58","DOI":"10.2307\/2308930","article-title":"The Double Dixie Cup Problem","volume":"67","author":"Newman","year":"1960","journal-title":"Am. Math. Mon."}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/10\/4\/334\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:42:10Z","timestamp":1760168530000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/10\/4\/334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,7]]},"references-count":7,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["axioms10040334"],"URL":"https:\/\/doi.org\/10.3390\/axioms10040334","relation":{},"ISSN":["2075-1680"],"issn-type":[{"type":"electronic","value":"2075-1680"}],"subject":[],"published":{"date-parts":[[2021,12,7]]}}}