Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
A Turing machine $T$ runs in polynomial time if there is a polynomial $p$ such that the running time of $T$ on an input of length $n$ bits is at most $p(n)$. The same definition works for other machine models such as the RAM machine.
Whether $O(M)$ is polynomial time or not depends on the way you encode the input. If the input is encoded in binary, then $O(M)$ isn't polynomial time, since the input could be of length as low as $O(\log M)$. If the input is encoded in unary (i.e., a number $x \geq 0$ is encoded as $1^x$) then $O(M)$ is polynomial time. It is part of the definition of the problem to specify the way the input is encoded.
