Pseudo-polynomial time: Difference between revisions
Esoth~enwiki (talk | contribs) No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
In [[computational complexity theory]], '''pseudo-polynomial time''' refers to the computation time of a problem where the time, ''m''(''n''), is no greater than a [[polynomial function]] of the [[problem size]] ''n'' and an additional property of the input ''k''. The most common use is to consider running times dependent on the ''value'' of some input, as opposed to its ''size''. |
In [[computational complexity theory]], '''pseudo-polynomial time''' refers to the computation time of a problem where the time, ''m''(''n''), is no greater than a [[polynomial function]] of the [[problem size]] ''n'' and an additional property of the input ''k''. The most common use is to consider running times dependent on the ''value'' of some input, as opposed to its ''size''. Therefore both problems in '''P''' and in '''NP-Complete''' could have pseudo-polynomial time algorithms. |
||
<blockquote>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.</blockquote>From Garey and Johnson's book |
|||
==References== |
|||
* M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. |
|||
<references/> |
|||
[[Category:Computational complexity theory]] |
[[Category:Computational complexity theory]] |
||
Revision as of 01:26, 2 October 2006
In computational complexity theory, pseudo-polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size n and an additional property of the input k. The most common use is to consider running times dependent on the value of some input, as opposed to its size. Therefore both problems in P and in NP-Complete could have pseudo-polynomial time algorithms.
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.
From Garey and Johnson's book
References
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.