Aachen 2019 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
AKPIK: Arbeitskreis Physik, moderne Informationstechnologie und Künstliche Intelligenz
AKPIK 2: Machine-learning methods and computing in particle physics
AKPIK 2.10: Talk
Tuesday, March 26, 2019, 17:30–17:40, H10
Solving the Np-complete Subset Sum Problem with an Electrical Circuit Using Physical Memristor Models — Karlheinz Ochs, Enver Solan, •Dennis Michaelis, and Maximilian Herbrechter — Ruhr-University Bochum, Bochum, Germany
Logic gates are the building blocks to set up any logical conjunction. To do so, they have predetermined input and output nodes. Subject to current research are self-organizing (SO) logic gates which can be operated ’backwards’, meaning that the role of input and output nodes can be reversed. With this functionality, mathematically complex problems, such as np-hard or even np-complete problems, can potentially be solved efficiently. Such problems are utilized for cryptographic systems, where many of today’s encryption techniques are based on the np-hard prime factorization. In the upcoming times of quantum computing, more sophisticated encryption techniques are required. One of the proposed methods for post-quantum systems in the literature is based on the np-complete subset sum problem. In this work, we show an electrical circuit that deploys models of real memristors to solve the subset sum problem for three 3-bit numbers. To this end, we utilize SO half- and full-adders, which consist of SO and- and xor-gates with HfO2-based resistive random access memory cells. These devices are known to have rapid switching behavior, making them a suitable choice for solving complex optimization problems in a short amount of time. This could indicate that methods based on the subset sum-problem might not be sufficient to ensure proper encryption of data since memcomputing techniques exist to solve this problem efficiently.