Order-Invariance of Two-Variable Logic is coNExpTime-complete
share
We establish coNExpTime-completeness of the problem of deciding order-invariance of a given two variable first-order formula, improving and significantly simplifying coTwoNExpTime bound by Zeume and Harwath.
READ FULL TEXT