1
(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 read many branching programs capture $NC_1$, and width poly$(n)$ ordered branching programs (a subset of read-once branching programs where the input variables are read in a known fixed order) capture the behavior of a logspace machine over ...
1
There are two results this could plausibly be which nicely contrast each other - they differ on whether we look at finite or infinite structures:
(Turing, following Godel) The validity problem for first-order logic on arbitrary structures in a sufficiently rich language is $\Sigma^0_1$-complete; for example, the set of (codes of) sentences true in every ...
Only top voted, non community-wiki answers of a minimum length are eligible