Order-Invariance of Two-Variable Logic is coNExpTime-complete
arXiv:2208.07577
Abstract
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.