Fractal Analysis of the Subset-Sum Problem

Ruben Horn, Daan van den Berg, Pieter Adriaans

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

It is known that the hardness of the (two-way) number partitioning problem (NPP) variant of the subset-sum problem (SSP) depends on the number and distribution of bits in the set of numbers, but beyond this, it is relatively unexplained for the SSP itself. Thus, we look at the solution space of various problem instances of the SSP using fractal analysis. Two methods to determine the dimension are used. Plotting the fractal dimension over the range and distributions of informational bits, we find that it is correlated with this linear model and also moderately correlated to the hardness of the NPP. This suggests that fractal analysis might be a useful tool in understanding the complexity of combinatorial problems and, we believe, may help further understand the hardness in NP. Finally, we introduce a thought experiment derived from the famous Hilbert’s hotel, which we call Hilbert’s hotel with elevators, to intuitively illustrate how the complexity of the solutions space and the computational hardness may relate across combinatorial problems.

Original languageEnglish
Title of host publicationIJCCI 2024 - Proceedings of the 16th International Joint Conference on Computational Intelligence - ECTA, Porto, Portugal, November 20-22, 2024
Subtitle of host publicationVolume 1
EditorsFrancesco Marcelloni, Kurosh Madani, Niki van Stein, Joaquim Joaquim
PublisherSciTePress
Pages261-268
Number of pages8
Volume1
ISBN (Print)9789897587214
DOIs
Publication statusPublished - 2024
Event16th International Joint Conference on Computational Intelligence, IJCCI 2024 - Porto, Portugal
Duration: 20 Nov 202422 Nov 2024

Conference

Conference16th International Joint Conference on Computational Intelligence, IJCCI 2024
Country/TerritoryPortugal
CityPorto
Period20/11/2422/11/24

Bibliographical note

Publisher Copyright:
© 2024 by SCITEPRESS – Science and Technology Publications, Lda.

Keywords

  • Fractal Analysis
  • Hilbert’s Hotel
  • NP-Hard
  • Number Partitioning Problem
  • Subset-Sum Problem

Fingerprint

Dive into the research topics of 'Fractal Analysis of the Subset-Sum Problem'. Together they form a unique fingerprint.

Cite this