Template:Strong and weak NP hardness
Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms
[edit]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 integers in binary coding.
- If a problem is strongly NP-hard, then it does not even have a pseudo-polynomial time algorithm. It also does not have a fully-polynomial time approximation scheme. An example is the 3-partition problem. Both strong NP-hardness and pseudo-polynomial time correspond to encoding the input integers in unary coding.
Template documentation | This template's documentation is missing, inadequate, or does not accurately describe its functionality or the parameters in its code. Please help add, expand, or improve it. |
- ↑ Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".