New answers tagged

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