This seminar paper is submitted as part of the academic requirements for the seminar on Complexity within the field of Theoretical Computer Science during the summer term 2024 at the University of Kassel.
Codes als Mengen von Bitstrings fester Länge sind von großer Bedeutung in der Datenübertragung. Dabei spielen sowohl minimale als auch überdeckende Codes eine wichtige Rolle, welche durch den sogenannten Radius bzw. den Covering Radius formalisiert werden. In diesem Zusammenhang ist insbesondere die Hamming-Distanz als Metrik von zentraler Relevanz. In der vorliegenden Ausarbeitung werden das Minimum-Radius-Problem (MR) sowie das Maximum-Covering-Radius-Problem (MCR) untersucht. Es wird sowohl die Äquivalenz der beiden Probleme als auch deren NP-Vollständigkeit gezeigt.
Ahmad Lowejatan Noori,
University of Kassel
[email protected]