The hardness of counting full words compatible with partial words

摘要

We present several problems regarding counting full words compatible with a set of partial words or with the factors of a partial word, and show that they are #P-complete. Some of these counting problems have NP-complete decision counterparts to which a hard variant of CNF-SAT is reduced parsimoniously; the rest are #P-complete problems that cannot be canonically associated to NP-complete decision problems. For these problems we assume that the set of symbols compatible with the wildcards equals the alphabet of the input partial word. When both a partial word and the cardinality of the alphabet compatible with the wildcard are given as input, we show that the central problem of counting the full words compatible with factors of the given partial word is also #P-complete. Finally, we propose a nontrivial exponential-time algorithm, working in polynomial space, useful to derive upper bounds for the time needed to solve the discussed problems.