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:
“Every time I get happy
the Nana-hex comes through.
Birds turn into plumber’s tools,
a sonnet turns into a dirty joke,
a wind turns into a tracheotomy,
a boat turns into a corpse....”
—Anne Sexton (1928–1974)