0

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.

Frax
  • 103
  • 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. – user253751 Jun 10 '22 at 17:56
  • (Well, that assumes the number of bits in each number is also a constant) – user253751 Jun 10 '22 at 17:56
  • What is n in your O(cn^c)? Isn't it the input size, e.g. c? – Mat Jun 10 '22 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 Jun 10 '22 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 Jun 10 '22 at 18:04
  • This site is mostly focused on (applied) software engineering. In the future, you might find that questions about computer science are typically a better fit on our [cs.se] sister site. But in this particular case you got good responses here, so no need to crosspost. – amon Jun 10 '22 at 21:09

1 Answers1

2

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

user253751
  • 4,873
  • 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 Jun 10 '22 at 18:17
  • @frax look up the halting problem. – candied_orange Jun 11 '22 at 01:58
  • 2
    @Frax: while (true); is very much a finite number of instructions. How long does it run? – Jörg W Mittag Jun 11 '22 at 07: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 <) – user253751 Jun 13 '22 at 08:53