Pattern Matching in Set Partitions is NP-Complete
From MaRDI portal
Publication:6348111
arXiv2009.00122MaRDI QIDQ6348111FDOQ6348111
Authors: Thomas L. Grubb 
Publication date: 31 August 2020
Abstract: In this note we show that pattern matching in permutations is polynomial time reducible to pattern matching in set partitions. In particular, pattern matching in set partitions is NP-Complete.
Partitions of sets (05A18) Complexity of computation (including implicit computational complexity) (03D15)
This page was built for publication: Pattern Matching in Set Partitions is NP-Complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348111)
