Strongly NP-complete

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 is a list of objects of specific sizes and a size for the binsthat must contain the objects -- these object sizes and bin size are numerical parameters.

A problem is said to be NP-hard or NP-complete in the strong sense (strongly NP-complete or NP-hard), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

Normally numerical parameters to a problem are given in binary notation, so a problem of input size n might contain parameters whose size is exponential in n. If weredefine the problem to have the parameters given in unary notation, then the parameters must be bounded by the input size. Thus strong NP-completeness or NP-hardness may also be defined as the NP-completeness or NP-hardness of this unary version of the problem.

For example, Bin packing is strongly NP-complete while the Knapsack problem is only weakly NP-complete. Thus the version of Bin packing where the object andbin sizes are integers bounded by a polynomial remains NP-complete, while the corresponding version of the Knapsack problem can be solved in polynomial time by
dynamic programming.

Unless P=NP, there is no fully polynomial-time approximation scheme (or FPTAS) for the strongly NP-complete problems. [M. R. Garey and D. S. Johnson. "Computers and Intractability: a Guide to the Theory of NP-Completeness". W.H. Freeman, New York, 1979.]

ee also

* weakly NP-complete

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Complete Adventurer —   Genre(s) Role playing game Publisher Wizards of the Coast …   Wikipedia

  • Complete graph — K7, a complete graph with 7 vertices Vertices n Edges …   Wikipedia

  • Strongly compact cardinal — In mathematical set theory, a strongly compact cardinal is a certain kind of large cardinal number; their existence can neither be proven nor disproven from the standard axioms of set theory.A cardinal kappa; is strongly compact if and only if… …   Wikipedia

  • Strongly minimal theory — In model theory a branch of mathematical logic a minimal structure is an infinite one sorted structure such that every subset of its domain that is definable with parameters is either finite or cofinite. A strongly minimal theory is a complete… …   Wikipedia

  • Strongly regular graph — Let G = (V,E) be a regular graph with v vertices and degree k . G is said to be strongly regular if there are also integers λ and μ such that:* Every two adjacent vertices have λ common neighbours.* Every two non adjacent vertices have μ common… …   Wikipedia

  • NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… …   Wikipedia

  • 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… …   Wikipedia

  • 3-partition problem — The 3 partition problem is an NP complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m… …   Wikipedia

  • Numerical 3-dimensional matching — is a strongly NP complete decision problem. It is given by three multisets of integers X, Y and Z, each containing k elements, and a bound b. The goal is to select a subset M of such that every integer in X, Y and Z occurs exactly once and that… …   Wikipedia

  • Pseudo-polynomial time — In computational complexity theory, a numeric algorithm runs in pseudo polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input its number of digits).An ExampleConsider… …   Wikipedia

Share the article and excerpts

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