# Weak NP-completeness

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Weak_NP-completeness
> Markdown URL: https://mediated.wiki/source/Weak_NP-completeness.md
> Source: https://en.wikipedia.org/wiki/Weak_NP-completeness
> Source revision: 1336602581
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computational complexity](/source/Analysis_of_algorithms), an [NP-complete](/source/NP-complete) (or [NP-hard](/source/NP-hard)) problem is '''weakly NP-complete''' (or weakly NP-hard) if there is an [algorithm](/source/algorithm) for the problem whose running time is [polynomial](/source/polynomial) in the dimension of the problem and the magnitudes of the data involved (provided these are given as [integer](/source/integer)s), rather than the [base-two logarithm](/source/Binary_logarithm)s of their magnitudes. Such algorithms have running times that are [exponential](/source/Exponential_function) functions of their input size and are therefore not considered [polynomial](/source/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](/source/knapsack_problem) can be solved by a [dynamic programming](/source/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](/source/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](/source/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](/source/subset_sum_problem).

The related term [strongly NP-complete](/source/strongly_NP-complete) (or unary NP-complete) refers to those problems that remain NP-complete even if the data are encoded in [unary](/source/unary_numeral_system), 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==
{{Reflist}}

Category:Weakly NP-complete problems
Category:Computational complexity theory
Category:Complexity classes

---
Adapted from the Wikipedia article [Weak NP-completeness](https://en.wikipedia.org/wiki/Weak_NP-completeness) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Weak_NP-completeness?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.