We all know the partitioning problem: Given a super-set S of integers, can we partition S into 2 subsets with the same sum. And of course this problem is NP-complete.
My question is - let's denote M as the sum of all numbers in S. Is O(M) considered to be polynomial in this case?
I will clarify: I want to prove that a certain problem is NP-hard, and in order to do so I use a reduction from partitioning that uses O(M) nodes in a graph. Is this considered to be a polynomial build?