m-sophistication
classification
💻 cs.CC
keywords
m-sophisticationboundedsophisticationupperadditivecoarsecomplexitylower
read the original abstract
The m-sophistication of a finite binary string x is introduced as a generalization of some parameter in the proof that complexity of complexity is rare. A probabilistic near sufficient statistic of x is given which length is upper bounded by the m-sophistication of x within small additive terms. This shows that m-sophistication is lower bounded by coarse sophistication and upper bounded by sophistication within small additive terms. It is also shown that m-sophistication and coarse sophistication can not be approximated by an upper or lower semicomputable function, not even within very large error.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.