In fact, for any deterministic system to be able to solve such hard problems, be it a sequential deterministic Turing machine or a continuous time dynamical system, exponential resources are required which can be in terms of time, hardware components, maximum magnitudes of variables or their precision 7, 18, 19, 20. Vertex coloring is also one of the most studied NP-hard combinatorial optimization problems not only for its significance in computational theory but also for its many real world applications like fault diagnosis 12, scheduling 13, 14, 15, resource allocation 16 Such problems are believed to be solved, or approximated, efficiently in natural processes because they can explore the solution space in a massively parallel manner 17.
This means that the best algorithms end up searching the whole domain set for at least some problem instances. Vertex coloring of graphs is a combinatorial optimization problem which is NP-hard (non-deterministic polynomial-time hard), unless P = NP. Combinatorial optimizations represent a problem class where an optimal value of a function, or its optimal point, needs to computed within a domain set which is discrete or combinatorial. In this paper, we report experimental evidence and the corresponding theoretical foundation for harnessing the continuous time dynamics of a system of coupled relaxation oscillators to solve vertex coloring of a random graphs, a combinatorial optimization problem of large-scale importance. This has motivated active research in alternative computing models, where dynamical systems have been shown to provide a fundamentally new platform to address these increasingly important problem classes 7, 8, 9, 10, 11. In spite of the success of the von Neumann computing architecture, its limitations become apparent 1, 2 when dealing with certain classes of problems such as associative computing 3, 4, optimizations 5, pattern matching and recognition 6. Processing is distributed in all parts of the machine memory and processors are integrated clear distinguishable atomic instructions are replaced by continuous time dynamics and information is encoded in physically meaningful quantities instead of their symbolic interpretations. On the contrary, computation in nature, our brain included, follows a radically different approach. Computation is carried out through a sequence of instructions with periodic loads and stores to the memory. The semiconductor industry is pivoted upon the Von Neumann computer architecture which implements the “Turing Machine” model of computation with a clear distinction between processing units and memory. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for graph coloring. The proposed VO 2 oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. Pairwise coupled VO 2 oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO 2 oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments.
Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO 2) to efficiently solve vertex coloring of graphs. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution.
Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient.
0 kommentar(er)
