For each language L (is contained in) 2~* and function t: N → N, we define another language t*L (is contained in) 2~*. We then prove that L ∈ NL/poly if and only if there exists k ∈ N such that the projections (n~k * L) ∩ 2~n are accepted by nondeterministic finite automata of size polynomial in n. Therefore, proving super-polynomial lower bounds for unrestricted nondeterministic branching programs reduces to proving super-polynomial lower bounds for oblivious read-once nondeterministic branching programs i.e. nondeterministic finite automata.
展开▼
