Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms
Assuming P ≠ NP, the following are true for computational problems on integers:[1]
If a problem is
weakly NP-hard, then it does not have a
weakly polynomial time algorithm (polynomial in the number of integers and the number of bits in the largest integer), but it may have a pseudopolynomial time algorithm (polynomial in the number of integers and the magnitude of the largest integer). An example is the
partition problem. Both weak NP-hardness and weak polynomial-time correspond to encoding the input agents in
binary coding.