# 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`

- (1, 1, 1, 1, 1, 1, 1, 1) ->
- 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.