Polygence Scholar2022
Arjun Kulkarni
Dougherty Valley High SchoolClass of 2024San Ramon, California
About
Projects
- "Pattern Matching in Poset Permutations is NP-Complete" with mentor Jesse (Sept. 17, 2022)
Project Portfolio
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.