Abstract
We show that permutation pattern matching of a permutation pi in a permutation tau is NP-complete even when pi has no decreasing subsequence of length 3 and tau has no decreasing subsequence of length 4. We also show that this hardness result is tight.