Abstract
Given n positive integers we show how to construct a proof that the number of subsets summing to a particular integer t equals a claimed quantity. The proof is of size View the MathML sourceO⁎(t), can be constructed in O⁎(t)O⁎(t) time and can be probabilistically verified in time View the MathML sourceO⁎(t) with at most 1/2 one-sided error probability. Here O⁎(⋅)O⁎(⋅) omits factors polynomial in the input size.
Original language | English |
---|---|
Pages (from-to) | 15-16 |
Number of pages | 2 |
Journal | Information Processing Letters |
Volume | 118 |
Issue number | Februari |
DOIs | |
Publication status | Published - 1 Feb 2017 |
Keywords
- Computational complexity
- Exact algorithms
- Merlin–Arthur protocol
- Probabilistic verification
- Subset sum