# Divide et Impera and P vs NP

Disclaimer: this is not an attempt at solving `P vs NP`, but a way for me to better understand the problem.

Let `¥(n)` be the Subset sum problem, `n` being the number of inputs.

Trivially, a brute force algorithm can solve `¥(n)` in `O(n2^n)`.

Let's Divide et Impera trying to solve the problem using `n P` algorithms:

First example, `n = 3`:

We want to find a subset which contains a sum to a fixed target `T`, we start by checking subsets of cardinality `1`, a single for loop will suffice to check every element in `O(n)`.

We next look at subsets of cardinality `2`, we exit the previous for loop, and a double for loop will check every pair in `O(2n^2)`.

Same for cardinality `3`, an `O(3n^{3})` algorithm will conclude the test.

(Important, it is irrelevant if there are better algorithms for some cases, the point is that we have solved `¥(3)` in `P`)

Inductively, `¥(c)` should be solvable in `O(cn^c)`, which is indeed a polynomial algorithm, impractical, but still in `P`.

Obviously `P vs NP` is still an open problem so I'm not here with a proof, I just want a clarification on my reasoning to better understand this interesting problem, thanks.

• It's even better: since 3 is a constant, ¥(3) is solvable in O(1)! Generally any problem with fixed size input is O(1), therefore it's in NP, and in P, and in L, and really, just about every complexity class that exists. That's why we don't bother talking about problems with constant-size inputs. Commented Jun 10, 2022 at 17:56
• (Well, that assumes the number of bits in each number is also a constant) Commented Jun 10, 2022 at 17:56
• What is `n` in your `O(cn^c)`? Isn't it the input size, e.g. `c`?
– Mat
Commented Jun 10, 2022 at 17:59
• @user253751 Uhm, but in the end switched to `c`, which can be as big as I want? Or the point is that because the induction is based on `O(1)` algorithms, the induction fails?
– Frax
Commented Jun 10, 2022 at 17:59
• @user253751 Perfect, that's what I was missing, thanks a lot. If you want, write that as an answer, I'll accept it.
– Frax
Commented Jun 10, 2022 at 18:04

Proving that something is true for all positive numbers does not prove that it is true for infinity. That is not a valid form of induction.

1 is a number, 2 is a number, 3 is a number, 4 is a number, ... no matter how high c gets, c is a number. Therefore infinity is a number. Wrong!

1 is not infinity, 2 is not infinity, 3 is not infinity, 4 is not infinity, ... no matter how high c gets, c is not infinity. Therefore infinity is not infinity. Wrong!

You can say that ¥'(c) is the subset sum problem (or any other problem) where the input must be equal or smaller than c. Because it's got a maximum size it's O(1). However long it takes to solve the problem in the worst case, it always takes that long or less, which is O(1).

¥'(1) is O(1), ¥'(2) is O(1), ¥'(3) is O(1), ¥'(4) is O(1), ..... does not prove that ¥'(infinity) is O(1).

• Last question: an algorithm is by definition a finite sequence of instructions, so isn't also useless to talk about infinity, as no algorithm can exist to solve an infinite number of inputs, because then it would contain an infinite number of instructions and stop being an algorithm?
– Frax
Commented Jun 10, 2022 at 18:17
• @frax look up the halting problem. Commented Jun 11, 2022 at 1:58
• @Frax: `while (true);` is very much a finite number of instructions. How long does it run? Commented Jun 11, 2022 at 7:11
• @Frax an algorithm for ¥'(n) is not an algorithm with n instructions, but rather an algorithm that is capable of solving the problem when the problem size is smaller than n (or equal to n... doesn't really matter whether you say <= or just <) Commented Jun 13, 2022 at 8:53