Dichotomy for orderings?
Gábor Kun, Jaroslav Nešetřil · Society for Industrial and Applied Mathematics eBooks · 2026
Fagin defined the class \(NP\) by the means of Existential Second-Order logic. Feder and Vardi expressed it (up to polynomial equivalence) by special fragments of Existential Second-Order logic (SNP), while the authors used forbidden expanded substructures (cf. lifts and shadows). Consequently, for such problems there is no dichotomy, unlike for CSPs.