An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp., $n$-NFA) is a UFA (resp., NFA) $A$ over alphabet $\{0,1\}$ such that $L(A) \subseteq \{0,1\}^n$. Without loss of generality, I will assume that such automata have exactly one initial state $q_I$ and one final state $q_F$ and that they are trimmed (meaning that each state is both accessible from $q_I$ and co-accessible from $q_F$). This implies in particular that all the paths from $q_I$ to some state $q$ have the same length. I am interested in the following decision problem:
INPUT: An $n$-UFA $A$, integer (or rational) weights $\beta_i \in \mathbb{N}$ for $1 \leq i \leq n$, and a threshold $t\in \mathbb{N}$.
OUTPUT: YES if there exists a word $w \in \{0,1\}^n$ such that $w \notin L(A)$ and $\sum_{i=1}^n w_i \beta_i \geq t$, NO otherwise.
Observe that this problem is in NP: guess a word $w \in \{0,1\}^n$, check in polynomial time that $w \notin L(A)$ and $\sum_{i=1}^n w_i \beta_i \geq t$ and accept if this is the case.
Question: is this problem NP-complete?
Some observations:
- If we replace “$w\notin L(A)$” by “$w\in L(A)$”, then the problem becomes solvable in polynomial time, even for NFAs. Indeed, given an $n$-NFA, we can easily compute by induction, for every state $q$ that is at distance $i$ from $q_I$, the quantity $\max_{w \in \{0,1\}^i \text{ s.t. } q \in \delta(q_I,w)}(\sum_{j=1}^i w_j \beta_j)$, where $\delta(q_I,w)$ is the set of states that can be reached from $q_I$ by reading $w$.
- If we consider the problem for NFAs instead of UFAs, then this is NP-complete. Indeed, if we let $\beta_i=1$ for $1 \leq i \leq n$ and $t=0$, then this is just asking if there exists a word of size $n$ that is not in the language, and there is an easy reduction from DNF falsifiability (the automaton nondeterministically branches to a gadget that checks a clause, or see this post for instance).
- If all the $\beta_i$s are equal, then this is PTIME. Indeed, in that case the problem is simply asking if there exists a word $w\in \{0,1\}^n$ of hamming weight $\geq \lceil \frac{t}{\beta} \rceil$ that is not in $L(A)$. But for $1 \leq j \leq n$, because $A$ is a UFA, we can easily compute in polynomial time the number of words $w \in \{0,1\}$ of hamming weight $j$ that are in $L(A)$, and so by a counting argument we can detect if one such word is missing. Hence, any hardness proof will need to use distinct $\beta_i$ values.
- As observed in the comments, this problem can be rephrased using special kinds of unambiguous (Max,+) automata (see e.g., Section 3 of Colcombet, Thomas, Unambiguity in automata theory), where all the edges that are at the same distance from the initial state have the same weight.
As for the context: ultimately, I would like to obtain superpolynomial lower bounds on the size of UFAs recognizing the complement of UFAs that recognize finite languages. Since this seems hard, I'd like to at least obtain this conditionally to P $\neq$ NP. So I came up with this problem which, if proven NP-complete, would show that we cannot complement a UFA recognizing a finite language in PTIME. Note that Raskin, Michael, A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton shows such a lower bound, but the UFAs that are used are cyclic, and the proof seems to crucially rely on this.
