Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

A Deterministic Polynomial-Time Algorithm for Subset Sum with Full Integer Support

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
Read More Add to Saved list
  • Additional Information
    • Publication Date:
      2025
    • Collection:
      Anglia Ruskin University: Figshare
    • Abstract:
      We present a deterministic, polynomial-time algorithm for the classical Subset Sum problem over the full range of signed integers. The method avoids backtracking, dynamic programming, or pseudo-polynomial recursion. It uses structured anchoring and filtration to explore candidate sets without exponential blowup. The algorithm supports negative and large values and is tested on inputs up to ten million elements, showing consistent polynomial behavior in time and space
    • Accession Number:
      10.6084/m9.figshare.29844779.v1
    • Online Access:
      https://doi.org/10.6084/m9.figshare.29844779.v1
      https://figshare.com/articles/preprint/A_Deterministic_Polynomial-Time_Algorithm_for_Subset_Sum_with_Full_Integer_Support/29844779
    • Rights:
      CC BY 4.0
    • Accession Number:
      edsbas.3F234AB