A short note on Merlin-Arthur protocols for subset sum

Research output: Working paperPreprintAcademic

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^*(\sqrt{t})$ of what the number of solutions is that can be constructed in $O^*(t)$ time and can be probabilistically verified in time $O^*(\sqrt{t})$ with at most constant error probability. Here, the $O^*()$ notation omits factors polynomial in the input size $n\log(t)$.
Original languageEnglish
PublisherarXiv
Pages1-2
DOIs
Publication statusPublished - 4 Feb 2016

Keywords

  • cs.CC
  • cs.DS

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