Non-solvable Groups Are Not in FO+MOD+MAJ_2 REG

摘要

Motivated by the open question whether TC~0 = NC~1 we consider the case of linear size TC~0. We use the connections between circuits, logic, and algebra, in particular the characterization of TC~0 in terms of finitely typed monoids. Applying algebraic methods we show that the word problem for finite non-solvable groups cannot be described by a FO+MOD+MAJ[REG] formula using only two variables. This implies a separation result of FO[REG]-uniform linear TC~0 from linear NC~1.