Fractal analysis of the subset-sum problem
Publication date
2024
Document type
Konferenzbeitrag
Author
Organisational unit
Conference
16th International Conference on Evolutionary Computation Theory and Applications (ECTA 2024), part of the 16th International Joint Conference on Computational Intelligence (IJCCI 2024) ; Porto, Portugal ; November 20–22, 2024
Publisher
SciTePress
Book title
Proceedings of the 16th International Joint Conference on Computational Intelligence
Volume (part of multivolume book)
1
First page
261
Last page
268
Part of the university bibliography
✅
Language
English
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.
Description
License: https://creativecommons.org/licenses/by-nc-nd/4.0/
Version
Published version
Access right on openHSU
Metadata only access