  Permutation Pattern Matching (or PPM) is a decision problem whose input is a
pair of permutations $\pi$ and $\tau$, represented as sequences of integers,
and the task is to determine whether $\tau$ contains a subsequence
order-isomorphic to $\pi$. Bose, Buss and Lubiw proved that PPM is NP-complete
on general inputs.
  We show that PPM is NP-complete even when $\pi$ has no decreasing subsequence
of length 3 and $\tau$ has no decreasing subsequence of length 4. This provides
the first known example of PPM being hard when one or both of $\pi$ and
$\sigma$ are restricted to a proper hereditary class of permutations.
  This hardness result is tight in the sense that PPM is known to be polynomial
when both $\pi$ and $\tau$ avoid a decreasing subsequence of length 3, as well
as when $\pi$ avoids a decreasing subsequence of length 2. The result is also
tight in another sense: we will show that for any hereditary proper subclass C
of the class of permutations avoiding a decreasing sequence of length 3, there
is a polynomial algorithm solving PPM instances where $\pi$ is from C and
$\tau$ is arbitrary.
  We also obtain analogous hardness and tractability results for the class of
so-called skew-merged patterns.
  From these results, we deduce a complexity dichotomy for the PPM problem
restricted to $\pi$ belonging to $Av(\rho)$, where $Av(\rho)$ denotes the class
of permutations avoiding a permutation $\rho$. Specifically, we show that the
problem is polynomial when $\rho$ is in the set {1, 12, 21, 132, 213, 231,
312}, and it is NP-complete for any other $\rho$.
