4.17.1 Subset Sum

Definition

Given natural numbers w₁,…,w_n and an integer W, is there a subset that adds up to exactly W?

Polynomial Certifier

Given natural numbers w₁,…,w_n and an integer W, is there a subset that adds up to exactly W?

• Input: Given natural numbers w₁,…,w_n and an integer W
• Certificate: A solution that adds up to exactly W.
• Certifier: We can add them and check if the value equals to W.
• Time Complexity: O(1).

Reduction from 3-SAT from simple case to general case

Given an instance Φ of 3-SAT, we construct an instance of Subset Sum as following:

Φ is satisfiable ⇒ there exists a subset that sums to W.

There exists a subset that sums to W ⇒ Φ is satisfiable.