Complejidad del problema de las palabras con la menor cantidad de letras distintas aceptadas por un autómata finito

Dado un autómata A finito (determinista o no determinista, no creo que esto tenga mucha importancia) y un umbral n , ¿acepta A una palabra que contenga como máximo n letras distintas?

(Por k letras diferentes quiero decir que aabaa tiene dos letras distintas, a y b .)

Mostré que este problema era NP-completo, pero mi reducción produce autómatas en los que aparece la misma letra en muchas transiciones.

Estoy bastante interesado en los casos en que cada letra aparece como máximo k veces en A, donde k es un parámetro fijo. ¿El problema sigue siendo NP completo?

Para k = 1, el problema es la ruta más corta, también lo es P. Para k = 2 no he podido mostrar membresía en P ni encontrar una prueba de dureza NP.

¿Alguna idea, al menos para k = 2?

cc.complexity-theory np-hardness automata-theory David Monniaux
fuente

Para , debe buscar resultados sobre el problema de paridad matroide: en.wikipedia.org/wiki/Matroid_parity_problem

k = 2

$k=2$

domotorp

Respuestas:

Es NP-duro para . La reducción es de 3-SAT- (2,2), lo que significa que cada cláusula contiene literales y cada literal aparece en la mayoría de las cláusulas. $k=3$ $3$ $2$

$k$ $st$ $n$

$s$ $n$ $n$ $2n$ $n$

domotorp
fuente

Esta es la reducción que estaba usando (de CNF-SAT) pero no sabía que 3-SAT- (2,2) también tenía NP completo, por lo tanto, mi comentario sobre las letras posiblemente muchas veces. ¡Gracias!

David Monniaux

Y, de hecho (¡debería haberlo pensado!), Una reducción de SAT a 3-SAT- (2,2) es solo un poco más complicada que la reducción habitual a 3CNF-SAT.

David Monniaux