A short note on Merlin-Arthur protocols for subset sum

DOI10.1016/J.IPL.2016.09.002MaRDI QIDQ344519zbMATH OpenOpenAlexFDO

Authors Jesper Nederlof

Publication date 23 November 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.01819

zbMATH Keywords

computational complexityexact algorithmsMerlin-Arthur protocolprobabilistic verificationsubset sum

Mathematics Subject Classification ID

Complexity of proofs (03F20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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^{\ast }(sqrtt)$ of what the number of solutions is that can be constructed in $O^{\ast }(t)$ time and can be probabilistically verified in time $O^{\ast }(sqrtt)$ with at most constant error probability. Here, the $O^{\ast }()$ notation omits factors polynomial in the input size $nlog(t)$.

Recommendations

• Succinct Certificates for Almost All Subset Sum Problems
• Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection
• On variations of the subset sum problem
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Selection of a large sum-free subset in polynomial time

Cites work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Dense subset sum may be the hardest
• How proofs are prepared at Camelot (extended abstract)
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• PRIMES is in P
• Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation

Cited in

(4)

• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• A faster algorithm for pigeonhole equal sums
• Improved space bounds for subset sum
• New algorithms for pigeonhole equal subset sum

This page was built for publication: A short note on Merlin-Arthur protocols for subset sum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344519)