Expressing Properties in Second and Third Order Logic: Hypercube Graphs and SATQBF

F. Ferrarotti, W. Ren, J. M. Turull Torres

It follows from the famous Fagin's theorem that all problems in NP are expressible in existential second-order logic (ESO), and vice versa. Indeed, there are well-known ESO charact…