Weak NP-completeness: Difference between revisions
imported>WikiGary (add) |
(update) |
||
| Line 1: | Line 1: | ||
In [[Analysis of algorithms|computational complexity]], an NP-complete (or NP-hard) problem is '''weakly NP-complete''' (or weakly NP-hard) if there is an [[Algorithm|algorithm]] for the problem whose running time is [[Polynomial|polynomial]] in the dimension of the problem and the magnitudes of the data involved (provided these are given as [[Integer|integer]]s), rather than the base-two | In [[Analysis of algorithms|computational complexity]], an NP-complete (or NP-hard) problem is '''weakly NP-complete''' (or weakly NP-hard) if there is an [[Algorithm|algorithm]] for the problem whose running time is [[Polynomial|polynomial]] in the dimension of the problem and the magnitudes of the data involved (provided these are given as [[Integer|integer]]s), rather than the [[Binary logarithm|base-two logarithm]]s of their magnitudes. Such algorithms are technically [[Exponential function|exponential]] functions of their input size and are therefore not considered [[Polynomial|polynomial]].<ref>M. R. Garey and D. S. Johnson. ''Computers and Intractability: a Guide to the Theory of NP-Completeness''. W.H. Freeman, New York, 1979.</ref> | ||
For example, the NP-hard [[Knapsack problem|knapsack problem]] can be solved by a [[Dynamic programming|dynamic programming]] algorithm requiring a number of steps polynomial in the size of the knapsack and the number of items (assuming that all data are scaled to be integers); however, the runtime of this algorithm is exponential time since the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and Johnson (1979) observed, “A [[Pseudo-polynomial time|pseudo-polynomial-time]] algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.” Another example for a weakly NP-complete problem is the [[Subset sum problem|subset sum problem]]. | For example, the NP-hard [[Knapsack problem|knapsack problem]] can be solved by a [[Dynamic programming|dynamic programming]] algorithm requiring a number of steps polynomial in the size of the knapsack and the number of items (assuming that all data are scaled to be integers); however, the runtime of this algorithm is exponential time since the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and Johnson (1979) observed, “A [[Pseudo-polynomial time|pseudo-polynomial-time]] algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.” Another example for a weakly NP-complete problem is the [[Subset sum problem|subset sum problem]]. | ||
The related term strongly NP-complete (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in [[Unary numeral system|unary]], that is, if the data are "small" relative to the overall input size.<ref>L. Hall. [http://www.esi2.us.es/~mbilbao/complexi.htm Computational Complexity]. The Johns Hopkins University.</ref> | The related term strongly NP-complete (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in [[Unary numeral system|unary]], that is, if the data are "small" relative to the overall input size.<ref>L. Hall. [http://www.esi2.us.es/~mbilbao/complexi.htm Computational Complexity] {{Webarchive|url=https://web.archive.org/web/20061207171343/http://www.esi2.us.es/~mbilbao/complexi.htm |date=2006-12-07 }}. The Johns Hopkins University.</ref> | ||
{{Strong and weak NP hardness}} | |||
==References== | ==References== | ||
Latest revision as of 07:17, 30 August 2025
In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard) if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial.[1]
For example, the NP-hard knapsack problem can be solved by a dynamic programming algorithm requiring a number of steps polynomial in the size of the knapsack and the number of items (assuming that all data are scaled to be integers); however, the runtime of this algorithm is exponential time since the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and Johnson (1979) observed, “A pseudo-polynomial-time algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.” Another example for a weakly NP-complete problem is the subset sum problem.
The related term strongly NP-complete (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in unary, that is, if the data are "small" relative to the overall input size.[2]
Template:Strong and weak NP hardness
References
- ↑ M. R. Garey and D. S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.
- ↑ L. Hall. Computational Complexity . The Johns Hopkins University.
 |  |
