Lemma 3.9 (efficiency half) — the exhaustive-search tree circuit is computable in polynomial time
OpenPPADSIS.SubexpSIS.searchRTC_polyTimeLet be the exhaustive-search tree circuit map PPADSIS_SubexpSIS_SearchRTC, which sends a Boolean circuit to a regular tree circuit . The map
from the description of a circuit to the description of its tree circuit is computable in polynomial time: one multi-stack Turing machine (Mathlib's FinTM2 model, as in the published PolyTimeComputable) maps the code of every circuit to the code of within a number of steps polynomial in the length of the input code.
This is the efficiency half of Lemma 3.9 ("computed from in polynomial time"). The construction is syntactic: copies the gates of , appends conjunctions, and repeats one fixed combining circuit with gates times, so its description has length polynomial in that of . Together with PPADSIS.SubexpSIS.searchRTC_spec it gives the milestone PPADSIS.SubexpSIS.lemma_3_9.
Formalization Note Polynomial time is PPSLattice.PolyTimeOn Circuit.enc (fun φ => (searchRTC φ).enc): it is required on every circuit, well formed or not, with descriptions Circuit.enc and RTC.enc.
import Mathlib import Definitions.Def_PPSLattice_PolyTimeOn import Definitions.Def_PPADSIS_SubexpSIS_SearchRTC
namespace PPADSIS.SubexpSIS theorem searchRTC_polyTime : PPSLattice.PolyTimeOn Circuit.enc (fun φ => (searchRTC φ).enc) := by sorry end PPADSIS.SubexpSIS