Polynomial-time exact interpolation postprocessing for Theorem 6.3
ProvedCountOrderings.NFree.interpolation_postprocess_polytimecounting-complexitylinear-extensions
A Cook–Levin transducer takes a packed exact-cover input word and list of reply words and computes the specified postprocessing in polynomial time. On a standing instance it constructs the sampled values of the common-denominator numerator and uses rational interpolation in , extracting the coefficient of . On malformed inputs it outputs zero. On the other instances it returns the exact-cover count by the degenerate-case rule.
Preamble
import Definitions.Def_CountOrderings_NFree_OracleReduction import Definitions.Def_CookLevin_Complexity
Formal statement
namespace CountOrderings.NFree
theorem interpolation_postprocess_polytime :
∃ finish : List Bool → List Bool, CookLevin.IsPolyTimeComputable finish ∧
∀ (x : List Bool) (replies : List (List Bool)),
finish (packWords (x :: replies)) = NPBinary.encodeNat (finishX3C x replies) := 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