In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input – its number of digits).
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.
Read more about Pseudo-polynomial Time: Example, Generalizing To Non-numeric Problems, See Also
Famous quotes containing the word time:
“A man in love is like a clipped coupon—it’s time to cash in.”
—Mae West (1892–1980)