Polynomial-time verification of an N-free linear extension
ProvedCountOrderings.NFree.nfree_certificate_polytimecounting-complexitylinear-extensions
On the published Cook–Levin machine model, there is a polynomial-time verifier for the row-major ranking certificate. It accepts precisely when the input encodes an N-free poset of height exactly three and the certificate is the permutation matrix of a linear extension.
Preamble
import Definitions.Def_CountOrderings_NFree_Certificate import Definitions.Def_CookLevin_Complexity
Formal statement
namespace CountOrderings.NFree
theorem nfree_certificate_polytime :
∃ V : List Bool → List Bool → Bool,
CookLevin.PolyTimeDecidable V ∧ ∀ x w, V x w = true ↔ IsLinExtCertificate x w := by sorry
end CountOrderings.NFreeSource
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission #1207, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1207.pdf, Appendix A.12, pp. 37–38 (PDF pp. 38–39), proof of Theorem 6.3