Skip to content

Pseudo-polynomial

  • An algorithm 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.