Volume 127, Number 3, August 2019
|Number of page(s)||5|
|Published online||11 September 2019|
Critical branching processes in digital memcomputing machines
Department of Physics, University of California, San Diego - La Jolla, CA 92093, USA
Received: 29 April 2019
Accepted: 24 July 2019
Memcomputing is a novel computing paradigm that employs time non-locality (memory) to solve combinatorial optimization problems. It can be realized in practice by means of non-linear dynamical systems whose point attractors represent the solutions of the original problem. It has been previously shown that during the solution search digital memcomputing machines go through a transient phase of avalanches (instantons) that promote dynamical long-range order. By employing mean-field arguments we predict that the distribution of the avalanche sizes follows a Borel distribution typical of critical branching processes with exponent . We corroborate this analysis by solving various random 3-SAT instances of the Boolean satisfiability problem. The numerical results indicate a power-law distribution with exponent , in very good agreement with the mean-field analysis. This indicates that memcomputing machines self-tune to a critical state in which avalanches are characterized by a branching process, and that this state persists across the majority of their evolution.
PACS: 05.65.+b – Self-organized systems
© EPLA, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.