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 language | English |
---|---|
Title of host publication | IJCCI 2024 - Proceedings of the 16th International Joint Conference on Computational Intelligence - ECTA, Porto, Portugal, November 20-22, 2024 |
Subtitle of host publication | Volume 1 |
Editors | Francesco Marcelloni, Kurosh Madani, Niki van Stein, Joaquim Joaquim |
Publisher | SciTePress |
Pages | 261-268 |
Number of pages | 8 |
Volume | 1 |
ISBN (Print) | 9789897587214 |
DOIs | |
Publication status | Published - 2024 |
Event | 16th International Joint Conference on Computational Intelligence, IJCCI 2024 - Porto, Portugal Duration: 20 Nov 2024 → 22 Nov 2024 |
Conference
Conference | 16th International Joint Conference on Computational Intelligence, IJCCI 2024 |
---|---|
Country/Territory | Portugal |
City | Porto |
Period | 20/11/24 → 22/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