Implementierung eines optimierten Algorithmus zum Subset-Sum-Problem nach Howgrave-Graham und Joux

Abstract

Diese Arbeit befasst sich mit der Analyse und Implementierung eines optimierten Algorithmus für das NP-vollständige Subset-Sum-Problem basierend auf den Forschungen von Howgrave-Graham und Joux (HGJ) im Jahre 2010. Zunächst wird das Problem in den Kontext der Komplexitätstheorie eingeordnet. Des Weiteren werden grundlegende historische Lösungsansätze von Horowitz und Sahni sowie Schroeppel und Shamir vorgestellt, um deren exponentiellen Laufzeit- und Speicherlimitierungen aufzuzeigen. Den Schwerpunkt bildet die detaillierte Analyse der HGJ-Algorithmen. Insbesondere wird ihre Innovation in Form von der Nutzung multipler Repräsentationen einer Lösung in Verbindung mit modularer Arithmetik zur erheblichen Reduzierung des Suchraums untersucht. Im praktischen Teil der Arbeit wird der einfache HGJ-Algorithmus in Python implementiert. Das Softwaredesign ist auf Modularität und Effizienz fokussiert. In einer empirischen Auswertung wird das Laufzeitund Speicherverhalten der Implementierung in Abhängigkeit von der Problemgröße und dem entscheidenden Steuerungsparameter 𝛽 untersucht. Die Ergebnisse bestätigen den im HGJPaper beschriebenen Zeit-Speicher-Kompromiss und belegen die praktische Überlegenheit gegenüber klassischen Verfahren.

This thesis deals with the analysis and implementation of an optimized algorithm for the NP-complete Subset Sum problem based on the research of Howgrave-Graham and Joux (HGJ) in 2010. First, the problem is placed in the context of complexity theory. Furthermore, fundamental historical solution approaches by Horowitz and Sahni as well as Schroeppel and Shamir are presented to demonstrate their exponential runtime and memory limitations. The main focus is the detailed analysis of the HGJ algorithms. In particular, their innovation, using multiple representations of a solution in conjunction with modular arithmetic to significantly reduce the search space, is examined. In the practical part of this work, the simple HGJ algorithm is implemented in Python. The software design is focused on modularity and efficiency. In an empirical evaluation, the runtime and memory behavior of the implementation is investigated in relation to the problem size and the crucial control parameter 𝛽. The results confirm the time-memory-trade-off described in the HGJ paper and demonstrate its practical superiority over classical methods.