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.[1]
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); however, the runtime of 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.” Another example for a weakly NP-complete problem is the subset sum problem.
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.[2]
Strong and weak NP-hardness vs. strong and weak polynomial-time algorithmsedit
Assuming P ≠ NP, the following are true for computational problems on integers:[3]
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.
^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. Computational Complexity. The Johns Hopkins University.
^Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".
January 01, 1970
weak, completeness, computational, complexity, complete, hard, problem, weakly, complete, weakly, hard, there, algorithm, problem, whose, running, time, polynomial, dimension, problem, magnitudes, data, involved, provided, these, given, integers, rather, than,. 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 1 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 however the runtime of 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 Another example for a weakly NP complete problem is the subset sum problem 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 2 Strong and weak NP hardness vs strong and weak polynomial time algorithms editAssuming P NP the following are true for computational problems on integers 3 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 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 Computational Complexity The Johns Hopkins University Demaine Erik Algorithmic Lower Bounds Fun with Hardness Proofs Lecture 2 Retrieved from https en wikipedia org w index php title Weak NP completeness amp oldid 1090336898, wikipedia, wiki, book, books, library,
