Pseudo-polynomial time

Not to be confused with Quasi-polynomial time.

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is bounded from above by a polynomial function of the two variables: the numeric value of the input (the largest integer present in the input) and the length of the input (the number of bits required to represent it).

In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless P = NP. The strong/weak kinds of NP-hardness are defined analogously.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.