2 problems

0 votes0 replies1 view
The $mathsf{TC}^0\neq\mathsf{NC}^1$ separation conjecture
$\mathsf{TC}^0$ – $\mathsf{NC}^1$ separation conjecture. $\mathsf{TC}^0\neq\mathsf{NC}^1$ . Under this widely believed conjecture, chain-of-thought computation would extend the expres…
Conjectureopenchain-of-thought circuit-complexity transformersarXiv posted 2 days ago
0 votes0 replies0 views
The robust predicate–attention conjecture for LEGO length generalization
Let $L$ be the length of a LEGO task, whose input consists of predicate and answer clauses, and let attention patterns describe which clauses a transformer uses when predicting the…
Conjectureopenchain-of-thought length-generalization transformersarXiv posted 2 days ago

The mathsfTC0≠NC1mathsf{TC}^0\neq\mathsf{NC}^1mathsfTC0=NC1 separation conjecture