<p>It is NP-hard for $k=3$.
The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.</p>

<p>First of all, for simplicity, let's admit honestly that this problem has not much to do with automata.
Your problem is equivalent to the following:
Given an edge-colored digraph where each color occurs at most $k$ times, is there an $st$ path that uses at most $n$ colors?</p>

<p>For the reduction, the graph starts from $s$ with a path of length $n$, where $n$ is the number of variables of the 3-SAT-(2,2) input.
Each edge of this path is present twice, and all $2n$ edges have a different color.
The colors used when traversing this path correspond to which variables are true.
After this path, there is another path whose length is the number of clauses.
Here every edge is thrice, where the colors correspond to the literals of the clause.
We can get to the end of this path using no extra colors (thus in total $n$) if and only if the 3-SAT-(2,2) input is satisfiable.</p>

CC BY-SA 3.0
2017-12-19T12:18:19.373Z
This is the reduction that I was using (from CNF-SAT) but I was unaware that 3-SAT-(2,2) was also NP-complete, thus my remark about letters occurring possibly many times. Thanks!
David Monniaux
CC BY-SA 3.0
2017-12-19T13:06:08.250Z
And, indeed (I should have thought about it!) a reduction from SAT to 3-SAT-(2,2) is only slightly more complicated than the usual reduction to 3CNF-SAT !
David Monniaux
CC BY-SA 3.0
2017-12-19T12:00:12.873Z
2017-12-19T12:00:12.873Z
domotorp
<p>Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold <em>n</em>, does A accept a word containing at most <em>n</em> distinct letters?</p>

<p>(By <em>k</em> different letters I mean that <em>aabaa</em> has two distinct letters, <em>a</em> and <em>b</em>.)</p>

<p>I showed this problem to be NP-complete, but my reduction produces automata in which the same letter appears on many transitions.</p>

<p>I'm rather interested in the cases where each letter appears at most <em>k</em> times in A, where <em>k</em> is a fixed parameter. Is the problem still NP-complete?</p>

<p>For <em>k</em>=1 the problem is just shortest path, so is P. For <em>k</em>=2 I've neither been able to show membership in P nor to find a proof of NP-hardness.</p>

<p>Any idea, at least for <em>k</em>=2 ?</p>

CC BY-SA 3.0
2017-12-20T02:53:31.480Z
For $k=2$, you should look into results about the matroid parity problem: https://en.wikipedia.org/wiki/Matroid_parity_problem
domotorp
<cc.complexity-theory><np-hardness><automata-theory>
Complexity of the problem of words with fewest distinct letters accepted by a finite automaton
David Monniaux
# Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

(Asked by: username_0 on 2017-12-19)

Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold *n*, does A accept a word containing at most *n* distinct letters?

(By *k* different letters I mean that *aabaa* has two distinct letters, *a* and *b*.)

I showed this problem to be NP-complete, but my reduction produces automata in which the same letter appears on many transitions.

I'm rather interested in the cases where each letter appears at most *k* times in A, where *k* is a fixed parameter. Is the problem still NP-complete?

For *k*=1 the problem is just shortest path, so is P. For *k*=2 I've neither been able to show membership in P nor to find a proof of NP-hardness.

Any idea, at least for *k*=2 ?

**Tags:** cc.complexity-theory, np-hardness, automata-theory

> **Comments:**
> **username_1**: For $k=2$, you should look into results about the matroid parity problem: https://en.wikipedia.org/wiki/Matroid_parity_problem  

---

## 1 answers

### Answer by username_1 on 2017-12-19. Score: 13 | Accepted answer

It is NP-hard for $k=3$.
The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.

First of all, for simplicity, let's admit honestly that this problem has not much to do with automata.
Your problem is equivalent to the following:
Given an edge-colored digraph where each color occurs at most $k$ times, is there an $st$ path that uses at most $n$ colors?

For the reduction, the graph starts from $s$ with a path of length $n$, where $n$ is the number of variables of the 3-SAT-(2,2) input.
Each edge of this path is present twice, and all $2n$ edges have a different color.
The colors used when traversing this path correspond to which variables are true.
After this path, there is another path whose length is the number of clauses.
Here every edge is thrice, where the colors correspond to the literals of the clause.
We can get to the end of this path using no extra colors (thus in total $n$) if and only if the 3-SAT-(2,2) input is satisfiable.

> **Comments:**
> **username_0**: This is the reduction that I was using (from CNF-SAT) but I was unaware that 3-SAT-(2,2) was also NP-complete, thus my remark about letters occurring possibly many times. Thanks!  
> **username_0**: And, indeed (I should have thought about it!) a reduction from SAT to 3-SAT-(2,2) is only slightly more complicated than the usual reduction to 3CNF-SAT !  

---

