Summary
the 2014 International Symposium on Nonlinear Theory and its Applications
2014
Session Number:C2L-B
Session:
Number:C2L-B2
Amoeba-inspired Heuristic Search for NP-complete Problem Solution at the Nanoscale
Masashi Aono, Song-Ju Kim, Seiya Kasai, Hiroyoshi Miwa, Makoto Narusex,
pp.499-502
Publication Date:2014/9/14
Online ISSN:2188-5079
Summary:
We formulated a heuristic search algorithm, AmoebaSAT, inspired by the spatiotemporal oscillatory dynamics of a single-celled amoeboid organism that exhibits sophisticated computing capabilities in adapting to its environment efficiently. AmoebaSAT finds a solution to an NP-complete problem, the satisfiability problem (SAT), at a speed that is dramatically faster than one of the conventionally known fastest stochastic local search methods for randomly generated 3-SAT instances. By implementing AmoebaSAT using various nanodevices, we aim to develop ultra-compact and ultra-low-power-consuming devices with ultra-fast computational speed.