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 NP-complete 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.
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][3] However, the converse fails: e.g. if P does not equal NP, knapsack with two constraints is not strongly NP-hard, but has no FPTAS even when the optimal objective is polynomially bounded.[4]
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.
Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms
Assuming P ≠ NP, the following are true for computational problems on integers:[5]
If a problem is weakly NP-hard, then it does not have a weakly polynomial time algorithm (polynomial in the number of integers and the number of bits in the largest integer), but it may have a pseudopolynomial time algorithm (polynomial in the number of integers and the magnitude of the largest integer). An example is the partition problem. Both weak NP-hardness and weak polynomial-time correspond to encoding the input agents in binary coding.
^H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer.{{cite book}}: CS1 maint: uses authors parameter (link)
^Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".
January 21, 2023
strong, completeness, computational, complexity, strong, completeness, property, computational, problems, that, special, case, completeness, general, computational, problem, have, numerical, parameters, example, input, packing, problem, list, objects, specific. 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 NP complete 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 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 3 However the converse fails e g if P does not equal NP knapsack with two constraints is not strongly NP hard but has no FPTAS even when the optimal objective is polynomially bounded 4 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 Strong and weak NP hardness vs strong and weak polynomial time algorithms EditAssuming P NP the following are true for computational problems on integers 5 If a problem is weakly NP hard then it does not have a weakly polynomial time algorithm polynomial in the number of integers and the number of bits in the largest integer but it may have a pseudopolynomial time algorithm polynomial in the number of integers and the magnitude of the largest integer An example is the partition problem Both weak NP hardness and weak polynomial time correspond to encoding the input agents in binary coding If a problem is strongly NP hard then it does not even have a pseudo polynomial time algorithm It also does not have a fully polynomial time approximation scheme An example is the 3 partition problem Both strong NP hardness and pseudo polynomial time correspond to encoding the input agents in unary coding References Edit Garey M R Johnson D S July 1978 Strong NP Completeness Results Motivation Examples and Implications Journal of the Association for Computing Machinery New York NY ACM 25 3 499 508 doi 10 1145 322077 322090 ISSN 0004 5411 MR 0478747 S2CID 18371269 Vazirani Vijay V 2003 Approximation Algorithms Berlin Springer pp 294 295 ISBN 3 540 65367 8 MR 1851303 Garey M R Johnson D S 1979 Victor Klee ed Computers and Intractability A Guide to the Theory of NP Completeness A Series of Books in the Mathematical Sciences San Francisco Calif W H Freeman and Co pp x 338 ISBN 0 7167 1045 5 MR 0519066 H Kellerer and U Pferschy and D Pisinger 2004 Knapsack Problems Springer a href Template Cite book html title Template Cite book cite book a CS1 maint uses authors parameter link Demaine Erik Algorithmic Lower Bounds Fun with Hardness Proofs Lecture 2 Retrieved from https en wikipedia org w index php title Strong NP completeness amp oldid 1107142190, wikipedia, wiki, book, books, library,
