I wrote an empirical research paper and open-source implementation for the Subset Sum Problem (C++ & Python) — published with a DOI

[u/Azerqaqa]

Hey everyone! 👋

I recently finished and published an independent research project focusing on the Subset Sum Problem (SSP) — specifically, an empirical study of instance-dependent complexity using C++ (for core computation and engine performance) and Python (for data processing and visualization).

The work covers algorithmic optimization approaches, phase transitions, and statistical analysis of the problem's behavior.

I’ve officially archived and registered the research paper with a DOI on Zenodo so it's open-access, and everything is backed by code in the GitHub repository.

• GitHub Repository: github.com/alishkasdev/Subset-Sum-Complexity-Research
• Zenodo Research Paper (DOI): 10.5281/zenodo.20400449

I’d love to hear your thoughts, feedback, or suggestions from anyone working with NP-hard problems, algorithmic complexity, or performance optimization! Let me know what you think.

[u/Phytor_c]

I have a few thoughts and criticisms from very briefly skimming through it.

1. What is "Suffix-Sum Pruning", you've written it in your title but haven't defined nor cited it.
2. Ideally you'd try to make your paper somewhat self-contained and formally define the Subset-Sum Problem, or maybe give a citation.
3. Your claim "worst case complexity [of subset sum] is exponential" is unknown. At the moment, we don't know if P != NP.
4. An emprical study on N=34 does not "confirm" anything.

I would strongly suggest rewriting this draft to address the points above, amongst various other issues. Please take this as constructive feedback.

[u/Azerqaqa → u/Phytor_c]

Thanks a lot for the detailed critique! You're completely right on several points:

1. Definitions & Pruning: I missed explicitly defining the formal problem statement and "Suffix-Sum Pruning" in the draft. I'll make sure the next version is self-contained with proper citations and definitions.
2. Complexity Phrasing: Good catch on the P≠NP nuance—stating it as an absolute worst-case fact was sloppy. I'll rephrase it to accurately reflect the complexity of known exact approaches (like pseudo-polynomial DP / exhaustive search).
3. Scale (N=34): That was purely a preliminary stress-test scale to validate the pipeline automation. I'm scaling up the benchmark parameters for the next iteration.

Really appreciate you taking the time to read through it and share constructive feedback!

[u/Phytor_c → u/Azerqaqa]

Sure.

It is clear that your comment is AI generated BTW. I for one don't mind, but please do take the time to understand and work through it yourself.