Divide et Impera and P vs NP

Question

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.

Answer 1

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).