Which features make the brain such a powerful and energy-efficient computing machine? Can we reproduce them in the solid state, and if so, what type of computing paradigm would we obtain? I will show that a machine that uses memory (time non-locality) to both process and store information, like our brain, and is endowed with intrinsic parallelism and information overhead – namely takes advantage, via its collective state, of the network topology related to the problem – has a computational power far beyond our standard digital computers [1, 2]. We have named this novel computing paradigm “memcomputing” [1, 2, 3, 4]. As examples, I will show the polynomial-time solution of prime factorization, the search version of the subset-sum problem [5], and approximations to the Max-SAT beyond the inapproximability gap [6] using polynomial resources and self-organizing logic gates, namely gates that self-organize to satisfy their logical proposition [5]. I will also show that these machines are described by a topological field theory, and they compute via an instantonic phase, implying that they are robust against noise and disorder [7]. The digital memcomputing machines we propose can be efficiently simulated, are scalableand can be easily realized with available nanotechnology components. Work supported in part by CMRR and MemComputing, Inc. (http://memcpu.com/).

[1] M. Di Ventra and Y.V. Pershin, Computing: the Parallel Approach, Nature Physics 9, 200 (2013).
[2]F. L. Traversa and M. Di Ventra, Universal Memcomputing Machines, IEEE Transactions on Neural Networks and Learning Systems 26, 2702 (2015).
[3] M. Di Ventra and Y.V. Pershin, Just add memory, Scientific American 312, 56 (2015).
[4] M. Di Ventra and F.L. Traversa, Memcomputing: leveraging memory and physics to compute efficiently, J. Appl. Phys. 123, 180901 (2018).
[5] F. L. Traversa and M. Di Ventra, Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines, Chaos: An Interdisciplinary Journal of Nonlinear Science 27, 023107 (2017).
[6] F. L. Traversa, P. Cicotti, F. Sheldon, and M. Di Ventra, Evidence of an exponential speed-up in the solution of hard optimization problems,Complexity 2018, 7982851 (2018).
[7] M. Di Ventra, F. L. Traversa and I.V. Ovchinnikov, Topological field theory and computing with instantons, Annalen der Physik 1700123 (2017).