# Partitioning in time complexity of the sum

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?

• – D.W.
May 14, 2018 at 6:46
• So in this case if my reduction is correct but is in O(M) it is not a polynomial reduction? May 14, 2018 at 6:53

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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.92141235,"math_prob":0.9954772,"size":1125,"snap":"2023-40-2023-50","text_gpt3_token_len":284,"char_repetition_ratio":0.14362177,"word_repetition_ratio":0.018779343,"special_character_ratio":0.2551111,"punctuation_ratio":0.084337346,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998965,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-09-24T00:28:34Z\",\"WARC-Record-ID\":\"<urn:uuid:67880497-f540-4229-ab3f-4be83250eacf>\",\"Content-Length\":\"154574\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d16210a1-d2f3-4df8-bc91-75072d46529e>\",\"WARC-Concurrent-To\":\"<urn:uuid:5c1051a9-0917-4bda-9b25-dabc52a550d0>\",\"WARC-IP-Address\":\"104.18.11.86\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/91880/partitioning-in-time-complexity-of-the-sum\",\"WARC-Payload-Digest\":\"sha1:3ZIJ25SCWPP6AJ43MVVKXF3QZOOJJOOV\",\"WARC-Block-Digest\":\"sha1:MYDV3FRWM5TN7L52XV3VIHYNXR42VECV\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-40/CC-MAIN-2023-40_segments_1695233506539.13_warc_CC-MAIN-20230923231031-20230924021031-00623.warc.gz\"}"}