Lemma 3.9 (circuit half) — exhaustive search is a polynomial-size regular tree circuit
ProvedPPADSIS.SubexpSIS.searchRTC_specLet be a well-formed Boolean circuit with exactly one output, of size (input wires plus gates), and let be the exhaustive-search tree circuit PPADSIS_SubexpSIS_SearchRTC. Then, for one constant exponent and every such :
- is a well-formed regular tree circuit in the sense of Definition 3.8;
- its address length is ;
- its size satisfies ;
- its output is the exhaustive-search result for :
This is the circuit half of Lemma 3.9: exhaustive search for the first satisfying assignment of is the output of a regular tree circuit of size with address length . Together with the polynomial-time computability of (PPADSIS.SubexpSIS.searchRTC_polyTime) it gives the milestone PPADSIS.SubexpSIS.lemma_3_9.
Formalization Note The output is compared with searchOutput, which writes as true :: a* and as false :: 0^n, and orders lexicographically through big-endian binary. The circuit accepts when its output list is [true].
import Mathlib import Definitions.Def_PPADSIS_SubexpSIS_SearchRTC
namespace PPADSIS.SubexpSIS
theorem searchRTC_spec : ∃ k : ℕ, ∀ φ : Circuit, φ.WF → φ.outs.length = 1 →
(searchRTC φ).WF ∧ (searchRTC φ).p = φ.nIn ∧ (searchRTC φ).size ≤ (φ.size + 2) ^ k ∧
(searchRTC φ).output = searchOutput φ.nIn (fun a => φ.eval a = [true]) := by sorry
end PPADSIS.SubexpSIS