A short note on Merlin-Arthur protocols for subset sum

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

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

Keywords

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

Fingerprint

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

Cite this