A short note on Merlin-Arthur protocols for subset sum

DOI10.1016/J.IPL.2016.09.002zbMath1392.68208arXiv1602.01819OpenAlexW2290722161MaRDI QIDQ344519

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 algorithmssubset sumprobabilistic verificationMerlin-Arthur protocol

Mathematics Subject Classification ID

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

Related Items (1)

Improved Merlin-Arthur protocols for central problems in fine-grained complexity

Cites Work

• Unnamed Item
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• PRIMES is in P
• Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
• Dense Subset Sum may be the hardest
• How Proofs are Prepared at Camelot

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