Expressibility at the machine level versus structure level: ESO universal Horn Logic and the class P

Prabhu Manyem

We show that ESO universal Horn logic (existential second logic where the first order part is a universal Horn formula) is insufficient to capture P, the class of problems decidabl…