In 1972, Richard Karp published a paper titled "Reducibility Among Combinatorial Problems," in which he demonstrated that 21 decision problems were NP-complete. What is fascinating is that, until this date, no one has conclusively proven whether these problems can be solved using a polynomial-time algorithm. In layman's terms: if one can find a polynomial-time solution to any of these problems, like the Boolean Satisfiability Problem (SAT), then a domino effect ensues, and all NP problems would collapse to being polynomial-time solvable. Conversely, disproving the polynomial-time solvability for one inherently disproves it for all.

Post Script - pretty much, this blog series is my proving exercises before my final exam for the postgraduate course that I took, DDA6050: Analysis of Algorithms, draws near. Through this series, I attempt to prove the NP-completeness of Karp's problems from the ground up without relying much on established proofs.

Challenge Progress

Knapsack (simplified)

Given:

an integer $n$
a set of non-negative integers $S = {a_{1}, \dots, a_{n}}$
an integer $K$

Task:

Decide whether there is a subset $P \subseteq S$ such that $\sum_{a_{i} \in P} = K$

Partition

Given:

an integer $n$
a set of non-negative integers ${a_{1}, \dots, a_{n}}$

Task:

Decide whether there is a subset $P \subseteq [1, n]$ such that $\sum_{i \in P} a_{i} = \sum_{i \in / P} a_{i}$

Partition is NP

The question of whether the Partition problem lies within NP can be addressed by examining the verification process for a potential solution, which we'll call a certificate. For the Partition problem, this certificate is a subset

KaTeX can only parse string typed expression

P

drawn from the indices

[1, n]

of the given set of integers.

To verify the certificate's correctness, we start by computing the sum of the integers that are indexed by

KaTeX can only parse string typed expression

P

, which we denote as

\sum_{i \in P} a_{i}

. In parallel, we also determine the sum of the integers that aren't indexed by

P

, represented by

\sum_{i \in / P} a_{i}

. Our main criterion for correctness then hinges on a straightforward comparison: are these two sums equal? If they are, our algorithm acknowledges the validity of the Partition and returns yes. If not, it simply returns no.

In terms of computational efficiency, this verification process is quite tractable. Calculating both summations takes linear time, specifically

KaTeX can only parse string typed expression

O (n)

, and comparing them is a constant-time operation. Because the entire verification process is polynomial in

n

, we can confidently state that the Partition problem is NP.

Partition is NP-hard by Knapsack

Let's consider a known NP-hard problem, Knapsack.

Given an instance of the simplified version of Knapsack problem with items

KaTeX can only parse string typed expression

S = {a_{1}, \dots, a_{n}}

and an integer

K

, we then construct an instance of the Partition problem as follows:

Compute $H$ , which is half of the sum of the items in $S$ , i.e., $H = \frac{1}{2} \sum_{a_{i} \in S} a_{i}$ .
Form a new set $\tilde{S} = S \cup {2 H + 2 K, 4 H}$ .

The result of this transformation is

KaTeX can only parse string typed expression

\tilde{S}

, the goal is to find a subset of

\tilde{S}

that sums to

\frac{( 2 H + ( 2 H + 2 K ) + 4 H )}{2} = 4 H + K

(

KaTeX can only parse string typed expression

\Rightarrow

) Suppose there is a solution to the Knapsack problem where a subset

P \subseteq S

that sums up to

K

. Then, a solution to the Partition problem must also exist, as we can assign

4 H

into

P

and

2 H + 2 K

to the other subset

S ∖ P

. This is confirmed as

\sum_{a_{i} \in P} + 4 H = 4 H + K = (2 H - K) + (2 H + 2 K) = \sum_{a_{i} \in S ∖ P} + (2 H + 2 K)

(

KaTeX can only parse string typed expression

\Leftarrow

) Conversely, if there is a subset of

\tilde{S}

that sums up to

4 H + K

, say

Q

, we may conclude that both

2 H + 2 K

and

4 H

elements are not in the same subset as

6 H + 2 K > 4 H + K

. If the element

4 H \in Q

; then,

\sum_{a_{i} \in Q ∖ 4 H} = K

, we found

Q ∖ 4 H

as our answer to the Knapsack problem. Otherwise, the element

2 H + 2 K \in Q

; then,

\sum_{a_{i} \in Q ∖ 2 H + 2 K} = 2 H - K

, which is the complement subset of the answer to the Knapsack problem.

This proves that

KaTeX can only parse string typed expression

x \in Knapsack

iff

f (x) \in Partition, \forall x \in {0, 1}^{*}

The transformation involves adding two numbers to

KaTeX can only parse string typed expression

S

, which can be done in a constant time. Additionally, calculating

H

requires summing over

S

, which is done in

O (n)

. Hence,

f

is a polynomial time transformation, which proves that the Partition problem is NP-hard.

Partition is NP-complete

Since the Partition problem is both in NP and NP-hard, we conclude that the Partition problem is NP-complete; hence, shown.

← Natural Parallelism: Disclosing Efficient Techniques for Image Processing Natural Parallelism: The Paradigm of Refined Matrix Multiplication →

1

10

11

12

13

14

15

16

17

18

19

2

20

2020-Fall

2021-Fall

2021-Spring

2021-Summer

2022-Fall

2022-Spring

2023-Fall

2023-Spring

2024-Spring

20K-smooth

20K-smooth (no image)

21

22

23

24

25

26

27

28

29

3

30

31

32

33

34

35

36

37

4

5

6

7

8

9

appendix

appendix

appendix

archive

BIO1001-General-Biology

bonus

bonus

bucketsort

CHM1001-General-Chemistry

collections

Competitive-Programming

components

cpu

CSC1001-Introduction-to-Computer-Science-Programming-Methodology

CSC1002-Computational-Laboratory

CSC3001-Discrete-Mathematics

CSC3002-Assignment-1-src

CSC3002-Assignment-2-src

CSC3002-Assignment-3-src

CSC3002-Assignment-4-src

CSC3002-Assignment-5-src

CSC3002-Assignment-6-src

CSC3002-Introduction-to-Computer-Science-Programming-Paradigms

CSC3050-Computer-Architecture

CSC3050-Project-1-assembler

CSC3050-Project-2-simulator

CSC3050-Project-3-verilog

CSC3050-Project-4-CPU

CSC3100-Data-Structures

CSC3150-Assignment-1

CSC3150-Assignment-2

CSC3150-Assignment-3