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:
“It is the time we have now, and all our wasted time sinks into the sea and is swallowed up without a trace. The past is dust and ashes, and this incommensurably wide way leads to the pragmatic and kinetic future.”
—John Ashbery (b. 1927)