Core polynomial-time closure under concatenation of encoded CNF formulas
ProvedCookLevin.polyTime_encodeFormula_append_corecook-levinformula-concatenationpoly-time
If and have polynomial-time encoded outputs and , then their formula concatenation is also computable in polynomial time.
Formal statement
import Definitions.Def_CookLevin_Reduction
open CookLevin
theorem CookLevin.polyTime_encodeFormula_append_core (f g : List Bool → Formula)
(hf : IsPolyTimeComputable (fun x => encodeFormula (f x)))
(hg : IsPolyTimeComputable (fun x => encodeFormula (g x))) :
IsPolyTimeComputable (fun x => encodeFormula (f x ++ g x)) := by sorrySource