2024/12/06 by Lixia Luo, Luo, Lixia, Chang-Heng Li +3
Environmental Science · Engineering · #Analysis of environmental and stochastic processes #Optimization and Packing Problems #Automated Road and Building Extraction
paper · pdf · doi:10.48550/arxiv.2412.04967
The Hidden Subset Sum Problem (HSSP) is a significant NP-complete problem in number theory and combinatorics, with applications in cryptography and AI privacy. For the (n,k)-complete HSSP, where a target multiset must be recovered from its all k-subset sums, existing algorithms face limitations due to high complexity or intractability. This paper proposes two deterministic algorithms: a brute-force approach, and a novel method leveraging symmetric polynomials and Vieta's formulas with O(∑u=1n p(u,≤ k)3+\binomnkn) complexity, where p(u,≤ k) counts the number of partitions of a positive integer u into at most k parts. The latter constructs an n-th degree polynomial via Vieta's formulas, whose roots correspond to the hidden multiset elements. Additionally, the discussion about the homogeneous symmetric polynomial rings is of independent interest.