Refined Kolmogorov complexity of analog, evolving and stochastic recurrent neural networks

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F25%3A00637283" target="_blank" >RIV/67985807:_____/25:00637283 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.ins.2025.122104" target="_blank" >https://doi.org/10.1016/j.ins.2025.122104</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ins.2025.122104" target="_blank" >10.1016/j.ins.2025.122104</a>

Result language

angličtina

Original language name

Refined Kolmogorov complexity of analog, evolving and stochastic recurrent neural networks

Original language description

Kolmogorov complexity measures the compressibility of real numbers. We provide a refined characterization of the hypercomputational power of analog, evolving, and stochastic neural networks based on the Kolmogorov complexity of their real weights, evolving weights, and real probabilities, respectively. First, we retrieve the infinite hierarchy of complexity classes of analog networks, defined in terms of the Kolmogorov complexity of their real weights. This hierarchy lies between the complexity classes P and P/poly. Next, using a natural identification between real numbers and infinite sequences of bits, we generalize this result to evolving networks, obtaining a similar hierarchy of complexity classes within the same bounds. Finally, we extend these results to stochastic networks that employ real probabilities as randomness, deriving a new infinite hierarchy of complexity classes situated between BPP and BPP/log⁎. Beyond providing examples of such hierarchies, we describe a generic method for constructing them based on classes of functions of increasing complexity. As a practical application, we show that the predictive capabilities of recurrent neural networks are strongly impacted by the quantization applied to their weights. Overall, these results highlight the relationship between the computational power of neural networks and the intrinsic information contained by their parameters

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Information Sciences

ISSN

0020-0255

e-ISSN

1872-6291

Volume of the periodical

711

Issue of the periodical within the volume

September 2025

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

24

Pages from-to

122104

UT code for WoS article

001456228400001

EID of the result in the Scopus database

2-s2.0-105000540781