Does Subset Sum Admit Short Proofs?

Michał Włodarczyk

We investigate the question whether Subset Sum can be solved by a polynomial-time algorithm with access to a certificate of length poly(k) where k is the maximal number of bits in…