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.