Capturing relational NEXPTIME with a fragment of existential third order logic

Abstract

We prove that the existential fragment Σ^(2,ω) 1 of the third order logic TO^ω captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines that work in NEXTIME r can simulate third order relational machines that work in NEXPTIME 3,r.

Keywords

• relational complexity
• third order logic
• expressibility of logics
• relational machines
• fixed point quantifiers