14 votes

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
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
2 votes

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,459

Only top scored, non community-wiki answers of a minimum length are eligible