, finite set
R
of strings from
.
such that each string
is a subsequence
of
w
, i.e. one can get
x
by taking away letters from
w
.
for some
unless
NP
[
192
].
A
PX
-complete if the size of the alphabet
is fixed [
192
]
and [
58
].
Variation in which the objective is to find the longest minimal common
supersequence (a supersequence that cannot be reduced to a shorter common
supersequence by removing a letter) is A
PX
-hard even over the binary alphabet,
and the
shortest maximal common non-supersequence problem
is A
PX
-hard even over the binary alphabet [
272
].
Variation in which the longest common subsequence is known is also
A
PX
-hard even over the binary alphabet [
90
].
Viggo Kann