8

It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?

Given an NFA and a natural number $n$, determine if there exists a word of length $n$ that is rejected by the NFA.

At first I thought that it is possible to prove this is NP-Hard by reducing the problem of checking if every word is accepted by an NFA to it, by checking every word length until hitting an upper bound. but according to Yuval Filmus in this question, the upper bound is exponential in the number of states of the NFA, so this reduction does not work.

Is there a valid reduction from a NP-Hard problem, or is this problem solvable in polynomial time?

Tal K
  • 113
  • 3
  • This problem sounds like it might be related to intersection non-emptiness for DFA's with bounded input string length. See the BDFAI problem defined in The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5196 – Michael Wehar Jan 19 '20 at 10:51
  • I suggest that you can reduce from BDFAI to your problem as follows. Given a set of DFA's and a number $k$. Complement the DFA's and then OR them together to make an NFA. The DFA's accept some string of length k if and only if there is a string of length $k$ not accepted by the NFA. – Michael Wehar Jan 19 '20 at 11:00

1 Answers1

7

Your problem is NP-hard, by reduction from 3SAT.

Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$. Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as follows. The $n$-bit input to the NFA is treated as an assignment to $x_1,\dots,x_n$. The NFA first nondeterministically selects one of the $m$ clauses. Then, it checks whether the input satisfies that clause, and if so, rejects; otherwise accepts. Note that if the input $x$ satisfies $\varphi$, then the NFA rejects; otherwise, the NFA accepts.

Now there exists an input to the NFA of length $n$ that causes the NFA to reject, if and only if there is a satisfying assignment for $\varphi$. That means that your problem is at least as hard as 3SAT.

D.W.
  • 12,054
  • 2
  • 34
  • 80
  • Why does the certificate have polynomial length? Does this not contradict the statement given in the linked question? – Daniel Jan 19 '20 at 17:06
  • @Daniel, you're right. For no reason whatsoever I had in my mind that $n$ was presented in unary, which was a pure invention on my part. I've corrected my answer. – D.W. Jan 19 '20 at 19:20