Capturing relational NEXPTIME with a Fragment of Existential Third Order Logic
José María Turull-Torres · Americanae (AECID Library) · 2015
We prove that the existential fragment Σ12,ω 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 NEXPTIMEr can simulate third order relational machines that work in NEXPTIME3,r.