Weakly NP-complete

Weakly NP-complete

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.

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). 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".”

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).

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. [http://www.esi2.us.es/~mbilbao/complexi.htm Computational Complexity] . The Johns Hopkins University.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Weakly compact cardinal — In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by harvtxt|Erdös|Tarski|1961; weakly compact cardinals are large cardinals, meaning that their existence can neither be proven nor disproven from the… …   Wikipedia

  • Weakly symmetric space — In mathematics, a weakly symmetric space is a notion introduced by the Norwegian mathematician Atle Selberg in the 1950s as a generalisation of symmetric space, due to Élie Cartan. Geometrically the spaces are defined as complete Riemannian… …   Wikipedia

  • Strongly NP-complete — In computational complexity, strong NP completeness is a property of computational problems that is a special case of NP completeness. Ageneral computational problem may have numerical parameters. For example, the input to the Bin packing problem …   Wikipedia

  • List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… …   Wikipedia

  • Knapsack problem — BKP redirects here. For other uses, see BKP (disambiguation). Example of a one dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to… …   Wikipedia

  • Orlicz–Pettis theorem — In functional analysis, the Orlicz–Pettis theorem is a theorem about convergence in Banach spaces. It is named for Władysław Orlicz and Billy James Pettis. The result was originally proven by Orlicz for weakly sequentially complete normed… …   Wikipedia

  • Modularity (networks) — For other uses, see Modularity. Modularity is one measure of the structure of networks or graphs. It measures the strength of division of a network into modules (also called groups, clusters or communities). Networks with high modularity have… …   Wikipedia

  • Glossary of topology — This is a glossary of some terms used in the branch of mathematics known as topology. Although there is no absolute distinction between different areas of topology, the focus here is on general topology. The following definitions are also… …   Wikipedia

  • Hilbert space — For the Hilbert space filling curve, see Hilbert curve. Hilbert spaces can be used to study the harmonics of vibrating strings. The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It… …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”