The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic

Flavio Ferrarotti, Senén González, Klaus-Dieter Schewe +1

Let ${\mathrm{SO}}^{plog}$ denote the restriction of second-order logic, where second-order quantification ranges over relations of size at most poly-logarithmic in the size…