Griddings of permutations and hardness of pattern matching

Vít Jelínek, Michal Opler, Jakub Pekárek

We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations $\tau$ (the `text') and $\pi$ (the `pa…