Memristive oscillatory circuits for resolution of NP-complete logic puzzles

Sudoku case

Conference paper (2020)

Authors

Theodoros Panagiotis Chatzinikolaou Democritus University of Thrace
Iosif Angelos Fyrigos Democritus University of Thrace
Rafailia Eleni Karamani Democritus University of Thrace
Vasileios Ntinas Democritus University of Thrace, Universitat Politecnica de Catalunya
George Dimitrakopoulos Democritus University of Thrace
S.D. Cotofana Computer Engineering - EEMCS
Georgios Ch Sirakoulis Democritus University of Thrace
Research Group
Computer Engineering (EEMCS) (TU Delft)
Memristor networks Memristor oscillators NP-Complete Logic Puzzles Sudoku
More Info
expand_more

Published Date

2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Quantum & Computer Engineering

Research Group

Computer Engineering

Abstract

Memristor networks are capable of low-power and massive parallel processing and information storage. Moreover, they have presented the ability to apply for a vast number of intelligent data analysis applications targeting mobile edge devices and low power computing. Beyond the memory and conventional computing architectures, memristors are widely studied in circuits aiming for increased intelligence that are suitable to tackle complex problems in a power and area efficient manner, offering viable solutions oftenly arriving also from the biological principles of living organisms. In this paper, a memristive circuit exploiting the dynamics of oscillating networks is utilized for the resolution of very popular and NP-complete logic puzzles, like the well-known “Sudoku”. More specifically, the proposed circuit design methodology allows for appropriate usage of interconnections' advantages in a oscillation network and of memristor's switching dynamics resulting to logic-solvable puzzle-instances. The reduced complexity of the proposed circuit and its increased scalability constitute its main advantage against previous approaches and the broadly presented SPICE based simulations provide a clear proof of concept of the aforementioned appealing characteristics.