Pseudo polynomial Algorithms

What is Pseudo polynomial?

An pseudo polynomial Algorithms whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo polynomial algorithm.

For example, Consider the problem of counting frequencies of all elements in an array of positive numbers. A pseudo polynomial time solution for this is to first find the maximum value, then iterate from 1 to maximum value and for each value, find its frequency in array. This solution requires time according to maximum value in input array, therefore pseudo polynomial. On the other hand, an algorithm whose time complexity is only based on number of elements in array (not value) is considered as polynomial time algorithm.

Pseudo polynomial and NP-Completeness

Some NP-Complete problems have Pseudo Polynomial time solutions.

For example, Dynamic Programming Solutions of 0-1 Knapsack, Subset-Sum and Partition problems are Pseudo Polynomial. NP complete problems that can be solved using a pseudo polynomial time algorithms are called weakly NP-complete.