{"repo":"alekzandren/sqlite-subset-sum-solver","free":true,"listed":false,"github":"https://github.com/alekzandren/sqlite-subset-sum-solver","clone":"git clone https://github.com/alekzandren/sqlite-subset-sum-solver.git","description":"Experimental Subset Sum solver for large integers using SQLite as an out-of-core storage engine.","language":"Python","stars":12,"topics":["algorithms","backend-engineering","computational-complexity","computer-science","cryptography","cybersecurity","datastructures","discrete-mathematics","fault-tolerance","fintech"],"license":null,"category":"security-tools","readme_excerpt":"Optimized Meet-in-the-Middle Subset Sum Solver )-purple.svg?style=flat-square) An academic-grade Python implementation of the Subset Sum Problem (SSP), transitioning from brute-force $O(2^n)$ to an optimized Meet-in-the-Middle (MITM) architecture. This solver is designed for high-precision computational research, ensuring $O(2^{n/2} \\cdot \\log 2^{n/2})$ complexity while maintaining absolute numerical integrity. --- Theoretical Framework & Methodology The solver addresses the NP-complete nature of the Subset Sum Problem by focusing on algorithmic efficiency and state-space management. 1. Algorithmic Complexity - Time Complexity: The engine achieves $O(2^{n/2} \\cdot \\log 2^{n/2})$ through a dual-phase execution: - Generation: Sub-sum spaces for two partitions are generated in $O(2^{n/2})$. - Intersection: Lookups are optimized using Hash Maps for $O(1)$ average-case access and the bisect module for $O(\\log N)$ binary search across sorted state spaces. - Space Complexity: $O(2^{n/2})$ to store the primary state space. 2. Numerical Integrity - Arbitrary-Precision Arithmetic: Unlike standard floating-point implementations susceptible to IEEE 754 bit-drift, this solver utilizes Python’s native arbitrary-precision integers. This ensures 100% accuracy for cryptographic-scale integers ($ 2^{256}$). - Rational Scaling: For fractional datasets, the framework is designed to utilize fractions.Fraction or integer scaling to maintain absolute precision without the overhead of decimal contex","default_branch":null,"files":null,"tree":[],"storefront":"/r/alekzandren","claimed":false,"request_supported":{"post":"https://gitbuyer.com/r/alekzandren/sqlite-subset-sum-solver/request-supported","requests":0},"note":"indexed from public GitHub; nothing is for sale on this page. Clone it from GitHub. Paid listings live at /search."}