Étant donné un automate A (déterministe ou non déterministe, je pense que cela n'a pas beaucoup d'importance) et un seuil n , A accepte-t-il un mot contenant au plus n lettres distinctes?
(Par k lettres différentes, je veux dire que aabaa a deux lettres distinctes, a et b .)
J'ai montré que ce problème était NP-complet, mais ma réduction produit des automates dans lesquels la même lettre apparaît sur de nombreuses transitions.
Je m'intéresse plutôt aux cas où chaque lettre apparaît au plus k fois dans A, où k est un paramètre fixe. Le problème est-il toujours NP-complet?
Pour k = 1, le problème est le chemin le plus court, tout comme P. Pour k = 2, je n'ai ni pu montrer l'appartenance à P ni trouver une preuve de dureté NP.
Une idée, au moins pour k = 2?
la source
Réponses:
Il est NP-difficile pour . La réduction est de 3-SAT- (2,2), ce qui signifie que chaque clause contient littéraux et chaque littéral se produit dans au plus clauses.k = 3 3 2
Tout d'abord, pour plus de simplicité, admettons honnêtement que ce problème n'a pas grand-chose à voir avec les automates. Votre problème est équivalent à ce qui suit: Étant donné un digraphe couleur bord où chaque couleur se produit dans la plupart fois, est - il un chemin que les utilisations au plus couleurs?k s t n
Pour la réduction, le graphique part de avec un chemin de longueur , où est le nombre de variables de l'entrée 3-SAT- (2,2). Chaque bord de ce chemin est présent deux fois et tous les bords ont une couleur différente. Les couleurs utilisées lors de la traversée de ce chemin correspondent aux variables qui sont vraies. Après ce chemin, il y a un autre chemin dont la longueur est le nombre de clauses. Ici, chaque bord est trois fois, où les couleurs correspondent aux littéraux de la clause. Nous pouvons arriver à la fin de ce chemin sans utiliser de couleurs supplémentaires (donc au total ) si et seulement si l'entrée 3-SAT- (2,2) est satisfaisable.s n n 2 n n
la source