Kernelization lower bound for Permutation Pattern Matching: No polynomial kernel unless NP is contained in co-NP/polyResearch Paper
A long ordering can contain a much shorter ordering without sharing any of its numerical values. What matters is the relative order of selected entries. Researchers studying permutation patterns ask both how many permutations avoid a prescribed pattern and how efficiently an occurrence can be found. The algorithmic question has a second dimension: whether a…