A short note on Merlin-Arthur protocols for subset sum

J. Nederlof

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)


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 languageEnglish
Pages (from-to)15-16
Number of pages2
JournalInformation Processing Letters
Issue numberFebruari
Publication statusPublished - 1 Feb 2017


  • Computational complexity
  • Exact algorithms
  • Merlin–Arthur protocol
  • Probabilistic verification
  • Subset sum


Dive into the research topics of 'A short note on Merlin-Arthur protocols for subset sum'. Together they form a unique fingerprint.

Cite this