|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Stochasticity in Algorithmic Statistics for Polynomial Timeстатья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 26 февраля 2018 г.
- Авторы: Milovanov Alexey, Vereshchagin Nikolay
- Сборник: 32nd Computational Complexity Conference
- Серия: Leibniz International Proceedings in Informatics (LIPIcs)
- Том: 79
- Год издания: 2017
- Место издания: Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing Saarbrücken/Wadern, Germany
- Первая страница: 17:1
- Последняя страница: 17:17
- DOI: 10.4230/LIPIcs.CCC.2017.17
- Аннотация: 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.
- Добавил в систему: Верещагин Николай Константинович