I have learned that the Partition problem is included in the NP-Hard problem. I have done some searching about this Problem and seem to not find the reason why is for a certain problem it cannot be concluded that P = NP for a certain algorithm.
If Partition problem can be solved in time 𝑂 (𝑛𝑀) where 𝑛 is the number of elements in the set, and 𝑀 is the sum of the absolute values of the elements in the set. Why based on these, it cannot be concluded that P = NP?
The definition of P and NP states that an algorithm (non-deterministic in case of NP) exists that runs in a polynomial time. The trick is that the argument of the polynomial is the size of the problem, which is defined as the number of bits that encode the problem instance.
The trick with the Partition problem is that numbers are exponential in terms of bits encoding them, so 𝑂(𝑛𝑀) is actually exponential in terms of the size of the encoding.
The class of NP-complete problems where a deterministic polynomial time algorithm exists where the argument of the polynomial is the sum of numbers that define the problem is called weakly NP-complete. Partition, backpack and similar are in this class.
Related Wikipedia entry: https://en.wikipedia.org/wiki/Weak_NP-completeness