13
$\begingroup$

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 ?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – David Monniaux Dec 19 '17 at 12:18
  • $\begingroup$ 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 ! $\endgroup$ – David Monniaux Dec 19 '17 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.