Class Description

SO[TC]: Second-Order logic with transitive closure

SO[TC] is to SO as FO[TC] is to FO. The TC operator can now also take second-order variable as argument.

In Descriptive complexity we can see thatSO[TC] is equal to PSPACE.

Linked From

SO[${\displaystyle t(n)}$]: Iterated Second-Order logic

SO[${\displaystyle t(n)}$] is to SO as FO[${\displaystyle t(n)}$] is to FO. But we now also have second-order quantifier in the quantifier block.

In Descriptive complexity we can see that :

• SO[${\displaystyle n^{O(1)}}$] is equal to PSPACE it is also another way to write SO(TC)
• SO[${\displaystyle 2^{n^{O(1)}}}$] is equal to EXPTIME it is also another way to write SO(LFP)

More about...