Dougherty Valley High SchoolClass of 2024San Ramon, California
- "Pattern Matching in Poset Permutations is NP-Complete" with mentor Jesse (Sept. 17, 2022)
Pattern Matching in Poset Permutations is NP-Complete
Started Mar. 11, 2022
Abstract or project description
The pattern matching for permutations (PPM) problem is a natural problem of interest in computer science. While it has been proven to be NP-complete, its natural generalization of pattern matching in poset permutations (PMPP) has been understudied in this regard. The generic version of PMPP is straightforward to prove to be NP-complete by reduction to PPM. On the other hand, even basic variants of PMPP such as that where all total orders are rejected are not so naturally reducible to PPM. Thus, we prove variants of PMPP such as these are also NP-complete.