Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?
It is known that for every pair of naturals numbers n,a such that n &lt;= a &lt;= 2^n, there exists a minimal NDFA with n states whose corresponding equivalent minimal dfa has a states (over a four letter alphabet).

See the paper here: Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet.

Abstract of the paper:


  We show that for all integers n and α
  such that n ≤ α ≤ 2^n, there exists a
  minimal nondeterministic finite
  automaton of n states with a
  four-letter input alphabet whose
  equivalent minimal deterministic
  finite automaton has exactly a states.
  It follows that in the case of a
  four-letter alphabet, there are no
  "magic numbers", i.e., the holes in
  the hierarchy. This improves a similar
  result obtained by Geffert for a
  growing alphabet of size n + 2 (Proc.
  7th DCFS, Como, Italy, 23-37).


So, I suppose the answer to your question is, no.