shuffle_product_problem (558B)
1 # Shuffle product problem 2 3 The [computational_problem], given [words] s1, ..., sk, and t, of [deciding] whether t is in the [shuffle] of s1, ..., sk 4 5 can be done with [dynamic_programming], which gives a [polynomial_time] [algorithm] if k is a constant 6 7 is [NP_hard] for unbounded k, in [warmuth1984complexity] 8 - see Problem 3 in [giraudo2016unshuffling] 9 10 [complete] for [XNLP], cf [bodlaender2026parameterized] 11 12 Up: [shuffle_membership] 13 14 See also: [shuffle_product], [shuffle_membership_language] 15 16 Aliases: shuffle membership word, shuffle membership words