Interface Focus • Vol 8 • No 6
Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems
October 2018 • F.C.M.J.M. van Delft, Giulia Ipolitti, Dan V. Nicolau, Ayyappasamy Sudalaiyadum Perumal, Ondřej Kašpar, Sara Kheireddine, Sebastian Wachsmann‐Hogiu, …
On-chip network-based computation, using biological agents, is a new hardware-embedded approach which attempts to find solutions to combinatorial problems, in principle, in a shorter time than the fast, but sequential electronic computers. This analytical review starts by describing the underlying mathematical principles, presents several types of combinatorial (including NP-complete) problems and shows current implementations of proof of principle developments. Taking the subset sum problem as example for in-dept…