“Strong NP-completeness”的意思、由来-开放百科全书

In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general 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 bins that must contain the objects—these object sizes and bin size are numerical parameters.

A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.^[1] A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it; in combinatorial optimization, particularly, the phrase "strongly NP-hard" is reserved for problems that are not known to have a polynomial reduction to another strongly NP-complete problem.

Normally numerical parameters to a problem are given in positional notation, so a problem of input size n might contain parameters whose size is exponential in n. If we redefine 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 0-1 Knapsack problem is only weakly NP-complete. Thus the version of bin packing where the object and bin sizes are integers bounded by a polynomial remains NP-complete, while the corresponding version of the Knapsack problem can be solved in pseudo-polynomial time by dynamic programming.

While weakly NP-complete problems may admit efficient solutions in practice as long as their inputs are of relatively small magnitude, strongly NP-complete problems do not admit efficient solutions in these cases. From a theoretical perspective any strongly NP-hard optimization problem with a polynomially bounded objective function cannot have a fully polynomial-time approximation scheme (or FPTAS) unless P = NP.^[2]

Some strongly NP-complete problems may still be easy to solve on average, but it's more likely that difficult instances will be encountered in practice.

See also

References

1. ^{{cite journal|last1=Garey|first1=M. R.|authorlink1=Michael R. Garey|last2=Johnson|first2=D. S.|authorlink2=David S. Johnson|title='Strong' NP-Completeness Results: Motivation, Examples, and Implications|journal =Journal of the Association for Computing Machinery|volume=25|issue=3|date=July 1978|issn =0004-5411|pages =499–508| url=http://doi.acm.org/10.1145/322077.322090|doi=10.1145/322077.322090|publisher=ACM|location=New York, NY|mr=478747}}
2. ^{{cite book | last = Vazirani | first = Vijay V. | title = Approximation Algorithms | publisher = Springer | year = 2003 | pages = 294–295 | location = Berlin | isbn = 3-540-65367-8|mr=1851303}}
3. ^{{cite book|last1=Garey|first1=M. R.|authorlink1=Michael R. Garey|last2=Johnson|first2=D. S.|authorlink2=David S. Johnson|title=A Guide to the Theory of NP-Completeness|year=1979 |isbn=0-7167-1045-5|pages=x+338|url=|doi=|series=A Series of Books in the Mathematical Sciences|editor=Victor Klee|publisher=W. H. Freeman and Co.|location=San Francisco, Calif.|mr=519066|ref=harv}}
4. ^{{cite book|authors= H. Kellerer and U. Pferschy and D. Pisinger| title = Knapsack Problems | publisher = Springer | year = 2004}}