Go to Polygence Scholars page
Arjun Kulkarni's cover illustration
Polygence Scholar2022
Arjun Kulkarni's profile

Arjun Kulkarni

Dougherty Valley High SchoolClass of 2024San Ramon, California



  • "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.