↓Skip to main content
  1. Notes/

Pseudo-polynomial algorithms

Equality of numbers

  • $O(n)$ in both binary and unary coding

Primality test

  • is $n$ divisible by $2, 3, \dots, \sqrt{n}$
  • sub-linear complexity with unary coding of $n$
  • exponential complexity with binary coding of $n$

Subset sum

  • INPUT: a set $S$ of $n$ numbers, number $H$
  • GOAL: subset of numbers from $S$ such that their sum is equal to $H$
  • ALGORITHM: test every subset, $O(2^n)$
  • input (1, 1, 1, 1, 1, 1, 1, 1) vs ($2^8$)
    • (1, 1, 1, 1, 1, 1, 1, 1) -> #1#1#1#1#1#1#1#1
    • ($2^8$) -> 11111111
  • the same length of the input, but different complexity!

We want to better characterize the input:

  • define an integer problem
  • characterize the input by length of the input (binary) $|x|$ + maximal number in the input $Max(x)$

Algorithm is pseudo-polynomial if $Time_A(x) \leq p(|x|, Max(x))$ for every $x \in \mathcal{U}$

Knapsack problem

  • $O(nH)$
    • $n$ - number of items
    • $H$ - sum over all $h_i$

There exist a strong NP-hard problems that cannot be solved by pseudo-polynomial algorithm, e.g. TSP.