# Tag Info

## Hot answers tagged cc.complexity-theory

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