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:
“I love the smell of napalm in the morning. You know, one time we had to hailbomb, for twelve hours, and when it was all over I walked up.... We didn’t find one of ‘em, not one stinking dink
body. That smell, you know, that gasoline smell. The whole hill. It smelled like ... victory.”
—John Milius, U.S. screenwriter, Francis Ford Coppola (b. 1939)