Polynomial-time oracle query generation for the edge-poset gadgets
ProvedCountOrderings.NFree.gadget_queries_polytimecounting-complexitylinear-extensions
Given the encoded indexed exact-cover instance, a Cook–Levin transducer produces a batch of queries in polynomial time. For a standing instance with triples and universe size , the replies in batch order are the binary-encoded counts of the edge posets for . The packed reply length is bounded by a polynomial in the input length.
Preamble
import Definitions.Def_CountOrderings_NFree_OracleReduction import Definitions.Def_CountOrderings_NFree_Encoding import Definitions.Def_CookLevin_Complexity
Formal statement
namespace CountOrderings.NFree
theorem gadget_queries_polytime :
∃ queries : List Bool → List (List Bool),
CookLevin.IsPolyTimeComputable (fun x => packWords (queries x)) ∧
(∀ x I, decodeX3C x = some I → I.Standing →
(queries x).length = interpolationDegree I + 1 ∧
∀ j : Fin (interpolationDegree I + 1),
∃ hw : ValidPosetCode ((queries x).getD j.val []),
Nonempty (decodePoset ((queries x).getD j.val []) hw ≃o posetP I (j.val + 1))) ∧
∃ c d : ℕ, ∀ x,
(packWords ((queries x).map
(fun w => NPBinary.encodeNat (nfreeHeight3LinExtCount w)))).length ≤
CookLevin.polyBound c d x.length := 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, §6, pp. 15–17, and Appendix A.12, pp. 37–38