<p>In the following paper, a regular expression <span class="math-container">$r$</span> over some alphabet <span class="math-container">$\Sigma$</span> is constructed that accepts the set <span class="math-container">$INVALC_{M,w}$</span> of invalid computations of a deterministic in-place Turing machine <span class="math-container">$M$</span> on an input <span class="math-container">$w$</span>, which makes at least <span class="math-container">$2^{|w|}$</span> steps on input <span class="math-container">$w$</span> before it halts. That is, if <span class="math-container">$M$</span> does not accept <span class="math-container">$w$</span>, then <span class="math-container">$INVALC_{M,w}$</span> is the universal language <span class="math-container">$\Sigma^*$</span>, and otherwise, exactly one word is missing from <span class="math-container">$INVALC_{M,w}$</span>.</p>
<blockquote>
<p>Gregor Gramlich, Georg Schnitger: Minimizing nfa's and regular
expressions. J. Comput. Syst. Sci. 73(6): 908-923 (2007)</p>
</blockquote>
<p>I think that this construction can be altered to show that your problem is PSPACE-complete in the case where the number <span class="math-container">$n$</span> is encoded in binary.</p>

CC BY-SA 4.0
2024-06-04T20:52:10.693Z
2024-06-04T20:52:10.693Z
Hermann Gruber
<p>Your problem is NP-hard, by reduction from 3SAT.</p>
<p>Let <span class="math-container">$\varphi$</span> be a 3SAT formula with <span class="math-container">$m$</span> clauses and on the <span class="math-container">$n$</span> variables <span class="math-container">$x_1,\dots,x_n$</span>.  Construct a NFA over the alphabet <span class="math-container">$\Sigma=\{0,1\}$</span> as follows.  The <span class="math-container">$n$</span>-bit input to the NFA is treated as an assignment to <span class="math-container">$x_1,\dots,x_n$</span>.  The NFA first nondeterministically selects one of the <span class="math-container">$m$</span> clauses.  Then, it checks whether the input satisfies that clause, and if so, rejects; otherwise accepts.  Note that if the input <span class="math-container">$x$</span> satisfies <span class="math-container">$\varphi$</span>, then the NFA rejects; otherwise, the NFA accepts.</p>
<p>Now there exists an input to the NFA of length <span class="math-container">$n$</span> that causes the NFA to reject, if and only if there is a satisfying assignment for <span class="math-container">$\varphi$</span>.  That means that your problem is at least as hard as 3SAT.</p>
<p>If <span class="math-container">$n$</span> is provided in unary, the problem is in NP.  In particular, given a word of length <span class="math-container">$n$</span>, it is easy to check in time polynomial in <span class="math-container">$n$</span> that it is rejected by the NFA.  My thanks to Joshua Grochow for <a href="https://cstheory.stackexchange.com/questions/46199/determining-if-a-word-of-specific-length-exists-that-is-not-accepted-by-a-nfa/46200?noredirect=1#comment121192_46200">pointing this out</a>.</p>
<p>It follows that if <span class="math-container">$n$</span> is provided in unary, your problem is NP-complete.</p>

CC BY-SA 4.0
2020-01-18T21:16:00.053Z
2024-06-03T01:26:28.427Z
2024-06-03T01:26:28.427Z
D.W.
<p>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?</p>

<p>Given an NFA and a natural number <span class="math-container">$n$</span>, determine if there exists a word of length <span class="math-container">$n$</span> that is rejected by the NFA.</p>

<p>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 <a href="https://cs.stackexchange.com/questions/83749/finding-non-trivial-nfa-that-accepts-all-short-strings">this question</a>, the upper bound is exponential in the number of states of the NFA, so this reduction does not work.</p>

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

CC BY-SA 4.0
2020-01-19T10:51:55.997Z
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
CC BY-SA 4.0
2020-01-19T11:00:40.187Z
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
<np-hardness><time-complexity><nondeterminism><nfa>
Determining if a word of specific length exists that is not accepted by a NFA
Tal K
# Determining if a word of specific length exists that is not accepted by a NFA

(Asked by: username_0 on 2020-01-18)

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](https://cs.stackexchange.com/questions/83749/finding-non-trivial-nfa-that-accepts-all-short-strings), 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?

**Tags:** np-hardness, time-complexity, nondeterminism, nfa
> **Comments:**
> **username_1**: 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  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2020-01-18. Score: 10 | Accepted answer

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](https://cstheory.stackexchange.com/questions/46199/determining-if-a-word-of-specific-length-exists-that-is-not-accepted-by-a-nfa/46200?noredirect=1#comment121192_46200).

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


---

### Answer by username_2 on 2024-06-04. Score: 3

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.


---

