New answers tagged

2 votes
Accepted

Straight-line program for sets

This problem is basically equivalent to the minimum AND-circuit problem. They ask for a minimum circuit that only use AND gates, and it tries to compute a set of monomials. A monomial is computed by ...
Chao Xu's user avatar
  • 4,449
8 votes

Complexity of NFA cofiniteness

Since the other answer makes it sound as if it were not obvious, let me point out that the problem is computable in PSPACE. First, we observe: Lemma. For any NFA $A$ with $n$ states, the following ...
Emil Jeřábek's user avatar
14 votes
Accepted

Complexity of NFA cofiniteness

Lemma 1. Determining whether a given NFA is cofinite is PSPACE-hard. Proof. The proof is by an easy reduction from the PSPACE-complete problem of determining whether a given NFA is universal. The ...
Neal Young's user avatar
  • 10.8k

Top 50 recent answers are included