Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length n contains a given pattern of length k. In this work we give two new algorithms for this well-studied problem, one whose running time is n (k/4+o(k)), and a polynomial-space algorithm whose running time is the better of O(1.618(n)) and O(n(k/2+1)). These results improve the earlier best bounds of n(0)(.)(47k)(+o(k)) and O(1.79(n)) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when k is an element of Omega(log n). We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time f(k).n(o(k/logk)) would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing (4321-avoiding) and 3-decreasing (1234-avoiding) permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes.
