10
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5196 $\endgroup$ Commented Jan 19, 2020 at 10:51
  • $\begingroup$ 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. $\endgroup$ Commented Jan 19, 2020 at 11:00

2 Answers 2

11
$\begingroup$

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.

If $n$ is provided in unary, the problem is in NP. In particular, given a word of length $n$, it is easy to check in time polynomial in $n$ that it is rejected by the NFA. My thanks to Joshua Grochow for pointing this out.

It follows that if $n$ is provided in unary, your problem is NP-complete.

$\endgroup$
9
  • 2
    $\begingroup$ Minor point but isn't this a coNP-hardness proof rather than an NP-hardness proof? This is giving a PTIME reduction from 3SAT to the complement of the universality problem (checking if an NFA is not universal) $\endgroup$
    – a3nm
    Commented Jun 1 at 19:43
  • 2
    $\begingroup$ @a3nm, Good point. I've revised my answer accordingly. Thank you for the correction. $\endgroup$
    – D.W.
    Commented Jun 1 at 21:16
  • 1
    $\begingroup$ Wait...checking if an NFA accepts/rejects a given string in deterministic polytime (in the size of the NFA and the size of the string), so the original problem is in NP (if n is given in unary)... $\endgroup$ Commented Jun 2 at 18:04
  • 3
    $\begingroup$ I think the comment of a3nm got you confused ;) for the original problem asking for a rejected word, you gave indeed a NP-hardness proof: $\exists$ rejected word $\Leftrightarrow$ formula satisfiable. This means the problem is indeed NP-complete. $\endgroup$
    – Denis
    Commented Jun 2 at 20:50
  • 1
    $\begingroup$ @Denis, thank you for helping me to sort this out. I appreciate it. $\endgroup$
    – D.W.
    Commented Jun 3 at 1:26
3
$\begingroup$

In the following paper, a regular expression $r$ over some alphabet $\Sigma$ is constructed that accepts the set $INVALC_{M,w}$ of invalid computations of a deterministic in-place Turing machine $M$ on an input $w$, which makes at least $2^{|w|}$ steps on input $w$ before it halts. That is, if $M$ does not accept $w$, then $INVALC_{M,w}$ is the universal language $\Sigma^*$, and otherwise, exactly one word is missing from $INVALC_{M,w}$.

Gregor Gramlich, Georg Schnitger: Minimizing nfa's and regular expressions. J. Comput. Syst. Sci. 73(6): 908-923 (2007)

I think that this construction can be altered to show that your problem is PSPACE-complete in the case where the number $n$ is encoded in binary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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