New answers tagged np-hardness
1
Your problem is NP-complete, 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,...
3
Yes, even in the purely existential case. See https://en.wikipedia.org/wiki/Existential_theory_of_the_reals
Top 50 recent answers are included
