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:
“... the present
A time traditionally soured,
A time unrecommended by event.”
—Philip Larkin (1922–1986)