2026-08-17T14:49:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7522 2024-03-06T10:40:12Z ddc:004 open_access

Stochasticity in Algorithmic Statistics for Polynomial Time Milovanov, Alexey Vereshchagin, Nikolay Algorithmic Statistics Kolmogorov complexity elusive set distinguishing complexity A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical hypothesis for Algorithmic Statistics with polynomial time bounds, which are called acceptability, plausibility and optimality. Roughly speaking, a probability distribution m is called an acceptable explanation for x, if x possesses all properties decidable by short programs in a short time and shared by almost all objects (with respect to m). Plausibility is a similar notion, however this time we require x to possess all properties T decidable even by long programs in a short time and shared by almost all objects. To compensate the increase in program length, we strengthen the notion of `almost all' - the longer the program recognizing the property is, the more objects must share the property. Finally, a probability distribution m is called an optimal explanation for x if m(x) is large. Almost all our results hold under some plausible complexity theoretic assumptions. Our main result states that for acceptability and plausibility there are infinitely many non-stochastic objects, i.e. objects that do not have simple plausible (acceptable) explanations. Using the same techniques, we show that the distinguishing complexity of a string x can be super-logarithmically less than the conditional complexity of x with condition r for almost all r (for polynomial time bounded programs). Finally, we study relationships between the introduced notions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexey Milovanov and Nikolay Vereshchagin 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.17 urn:nbn:de:0030-drops-75222 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode