Template:Strong and weak NP hardness: Difference between revisions
From Vigyanwiki
(Created page with "== Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms == Assuming P ≠ NP, the following are true for computational problems on integers:<ref>{{cite w...") |
m (1 revision imported from alpha:Template:Strong_and_weak_NP_hardness) |
Latest revision as of 13:03, 10 August 2023
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.
- 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 agents in unary coding.
Template documentation
 | This template's documentation is missing, inadequate, or does not accurately describe its functionality and/or the parameters in its code. Please help to expand and improve it. |
[[Category:Template documentation pages{{#translation:}}]]
- ↑ Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".
