Pattern Matching in Set Partitions is NP-Complete

MaRDI QIDQ6348111zbMATH OpenFDO

Authors Thomas L. Grubb

Publication date 31 August 2020

Mathematics Subject Classification ID

Partitions of sets (05A18) Complexity of computation (including implicit computational complexity) (03D15)

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.

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)