2016/02/04 by Jesper Nederlof, Nederlof, Jesper
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1602.01819
openalex publication_date 2016/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the subset sum problem we are given n positive integers along with a target integer t. A solution is a subset of these integers summing to t. In this short note we show that for a given subset sum instance there is a proof of size O^*(√(t)) of what the number of solutions is that can be constructed in O^*(t) time and can be probabilistically verified in time O^*(√(t)) with at most constant error probability. Here, the O^*() notation omits factors polynomial in the input size nlog(t).