Files

319 lines
14 KiB
Lean4
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
/-
Released under Apache 2.0 license as described in the file LICENSE.
-/
import FormalConflictRange.FiniteCountDecider
/-!
# A lazy activity oracle
The exact oracle `activeComputable` decides activity by enumerating, for every DNF
alternative, one violated constraint, and then testing the resulting finite count
system. That product is correct but needlessly large: for the characterizing DNF
the alternatives share almost all of their constraints.
This file replaces the eager product by a lazy search for a *hitting set* of
constraints: one constraint from every alternative, but without repeating a
constraint that has already been selected. A partial selection is tested for
count feasibility before it is extended; infeasible prefixes are discarded, since
adding more violated constraints can only make the count system harder.
-/
namespace FormalConflictRange
/-! ## Hitting sets versus choices -/
/-- A list of constraints hits an alternative when one of the alternative's
constraints occurs in the list. -/
def Hits (B : List Constraint) (S : ConstraintSystem) : Prop :=
∃ c ∈ S, c ∈ B
/-- A list of constraints hits every alternative of a DNF. -/
def HitsAll (B : List Constraint) (D : ConstraintDNF) : Prop :=
∀ S ∈ D, Hits B S
/-- Every `ChoosesAll` selection is a hitting set. -/
theorem hitsAll_of_choosesAll {bad : List Constraint} {D : ConstraintDNF}
(h : ChoosesAll bad D) : HitsAll bad D := by
induction D generalizing bad with
| nil => intro S hS; simp at hS
| cons S Ss ih =>
cases bad with
| nil => simp [ChoosesAll] at h
| cons c cs =>
rcases h with ⟨hcS, htail⟩
intro S' hS'
rcases List.mem_cons.mp hS' with rfl | hS'
· exact ⟨c, hcS, by simp⟩
· obtain ⟨c', hc'S', hc'bad⟩ := ih htail S' hS'
exact ⟨c', hc'S', by simp [hc'bad]⟩
/-- A hitting set contains a `ChoosesAll` selection: choose one hit from each
alternative, in order. -/
theorem exists_choices_subset {D : ConstraintDNF} {B : List Constraint}
(h : HitsAll B D) :
∃ bad : List Constraint, bad ∈ choices D ∧ ∀ c ∈ bad, c ∈ B := by
induction D with
| nil => exact ⟨[], by simp [choices], by simp⟩
| cons S Ss ih =>
obtain ⟨c, hcS, hcB⟩ := h S (by simp)
obtain ⟨bad, hbad, hsub⟩ := ih (fun S' hS' => h S' (by simp [hS']))
refine ⟨c :: bad, ?_, ?_⟩
· simp only [choices, List.mem_flatMap, List.mem_map]
exact ⟨c, hcS, bad, hbad, rfl⟩
· intro d hd
rcases List.mem_cons.mp hd with rfl | hd
· exact hcB
· exact hsub d hd
/-! ## Monotonicity of count feasibility -/
/-- Adding violated constraints cannot make a count system feasible. -/
theorem CountFeasible.mono {bounds : List Key} {k : Key} {S : ConstraintSystem}
{bad bad' : List Constraint} (hsub : ∀ c ∈ bad, c ∈ bad')
(h : CountFeasible bounds k S bad') : CountFeasible bounds k S bad := by
obtain ⟨counts, topCount, hfit, hS, hbad⟩ := h
exact ⟨counts, topCount, hfit, hS, fun c hc => hbad c (hsub c hc)⟩
/-! ## The lazy search -/
/-- Lazy search for a feasible hitting set. The accumulator `acc` already hits
the alternatives processed so far; a new constraint is added only when the
current alternative is not yet hit, and a prefix is abandoned as soon as its
count system is infeasible. -/
def searchBad (bounds : List Key) (k : Key) (S : ConstraintSystem) :
ConstraintDNF → List Constraint → Bool
| [], acc => countFeasibleBool bounds k S acc
| S' :: Ss, acc =>
if S'.any (fun c => decide (c ∈ acc)) then
searchBad bounds k S Ss acc
else
S'.any fun c =>
countFeasibleBool bounds k S (c :: acc) &&
searchBad bounds k S Ss (c :: acc)
/-- The search finds a feasible hitting set extending the accumulator. -/
theorem searchBad_spec (bounds : List Key) (k : Key) (S : ConstraintSystem)
(D : ConstraintDNF) (acc : List Constraint)
(hnoBot : ([] : Key) ∉ bounds) (hle : BoundsLe ([] : Key) bounds)
(hk : k = ([] : Key) ∨ k ∈ bounds) (hka : keyAfter k ∈ bounds)
(hcoverS : ∀ c ∈ S, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hcoverD : ∀ S' ∈ D, ∀ c ∈ S',
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hcoverAcc : ∀ c ∈ acc,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds) :
searchBad bounds k S D acc = true ↔
∃ B : List Constraint, (∀ c ∈ acc, c ∈ B) ∧ HitsAll B D ∧
CountFeasible bounds k S B := by
induction D generalizing acc with
| nil =>
constructor
· intro h
exact ⟨acc, fun _ hc => hc, by intro S' hS'; simp at hS',
(countFeasibleBool_spec bounds k S acc hnoBot hle hcoverS hcoverAcc hk hka).mp h⟩
· rintro ⟨B, haccB, -, hB⟩
exact (countFeasibleBool_spec bounds k S acc hnoBot hle hcoverS hcoverAcc hk hka).mpr
(CountFeasible.mono haccB hB)
| cons S' Ss ih =>
by_cases hcover : ∃ c ∈ S', c ∈ acc
· have hany : S'.any (fun c => decide (c ∈ acc)) = true := by
rw [List.any_eq_true]
obtain ⟨c, hcS', hcacc⟩ := hcover
exact ⟨c, hcS', by simp [hcacc]⟩
rw [searchBad, ite_eq_left hany]
obtain ⟨c, hcS', hcacc⟩ := hcover
have hcoverSs : ∀ S'' ∈ Ss, ∀ c ∈ S'',
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds :=
fun S'' hS'' c hc => hcoverD S'' (by simp [hS'']) c hc
have ih' := ih acc hcoverSs hcoverAcc
constructor
· intro hsearch
obtain ⟨B, haccB, hhits, hfeas⟩ := ih'.mp hsearch
exact ⟨B, haccB, fun S'' hS'' => by
rcases List.mem_cons.mp hS'' with hS | hS''
· subst S''
exact ⟨c, hcS', haccB c hcacc⟩
· exact hhits S'' hS'', hfeas⟩
· rintro ⟨B, haccB, hhits, hfeas⟩
exact ih'.mpr ⟨B, haccB,
fun S'' hS'' => hhits S'' (List.mem_cons_of_mem _ hS''), hfeas⟩
· have hany : S'.any (fun c => decide (c ∈ acc)) = false := by
rw [List.any_eq_false]
intro c hcS' hcacc
exact hcover ⟨c, hcS', by simpa using hcacc⟩
rw [searchBad, ite_eq_right (by simp [hany])]
constructor
· intro hsearch
rw [List.any_eq_true] at hsearch
obtain ⟨c, hcS', hboth⟩ := hsearch
rw [Bool.and_eq_true] at hboth
obtain ⟨hcfeas, htail⟩ := hboth
have hcoverAcc' : ∀ d ∈ c :: acc,
EndpointCovered d.lo bounds ∧ EndpointCovered d.hi bounds := by
intro d hd
rcases List.mem_cons.mp hd with hdc | hd
· rw [hdc]
exact hcoverD S' (by simp) c hcS'
· exact hcoverAcc d hd
have hfeasAcc : CountFeasible bounds k S (c :: acc) :=
(countFeasibleBool_spec bounds k S (c :: acc) hnoBot hle hcoverS
hcoverAcc' hk hka).mp hcfeas
have hcoverSs : ∀ S'' ∈ Ss, ∀ d ∈ S'',
EndpointCovered d.lo bounds ∧ EndpointCovered d.hi bounds :=
fun S'' hS'' d hd => hcoverD S'' (by simp [hS'']) d hd
obtain ⟨B, haccB, hhits, hfeas⟩ :=
(ih (c :: acc) hcoverSs hcoverAcc').mp htail
exact ⟨B, fun d hd => haccB d (List.mem_cons_of_mem _ hd),
fun S'' hS'' => by
rcases List.mem_cons.mp hS'' with hS | hS''
· subst S''
exact ⟨c, hcS', haccB c (by simp)⟩
· exact hhits S'' hS'', hfeas⟩
· rintro ⟨B, haccB, hhits, hfeas⟩
obtain ⟨c, hcS', hcB⟩ := hhits S' (by simp)
have hcacc : c ∉ acc := by
intro hcacc
exact hcover ⟨c, hcS', by simpa using hcacc⟩
have hsub : ∀ d ∈ c :: acc, d ∈ B := by
intro d hd
rcases List.mem_cons.mp hd with hdc | hd
· rw [hdc]
exact hcB
· exact haccB d hd
have hcoverAcc' : ∀ d ∈ c :: acc,
EndpointCovered d.lo bounds ∧ EndpointCovered d.hi bounds := by
intro d hd
rcases List.mem_cons.mp hd with hdc | hd
· rw [hdc]
exact hcoverD S' (by simp) c hcS'
· exact hcoverAcc d hd
have hcfeas : countFeasibleBool bounds k S (c :: acc) = true :=
(countFeasibleBool_spec bounds k S (c :: acc) hnoBot hle hcoverS
hcoverAcc' hk hka).mpr (CountFeasible.mono hsub hfeas)
have hcoverSs : ∀ S'' ∈ Ss, ∀ d ∈ S'',
EndpointCovered d.lo bounds ∧ EndpointCovered d.hi bounds :=
fun S'' hS'' d hd => hcoverD S'' (by simp [hS'']) d hd
have htail : searchBad bounds k S Ss (c :: acc) = true :=
(ih (c :: acc) hcoverSs hcoverAcc').mpr
⟨B, fun d hd => by
rcases List.mem_cons.mp hd with hdc | hd
· rw [hdc]
exact hcB
· exact haccB d hd,
fun S'' hS'' => hhits S'' (List.mem_cons_of_mem _ hS''), hfeas⟩
rw [List.any_eq_true]
exact ⟨c, hcS', by rw [Bool.and_eq_true]; exact ⟨hcfeas, htail⟩⟩
/-- On the canonical bounds, the lazy search is exactly the eager `choices`
enumeration. -/
theorem searchBad_choices (bounds : List Key) (k : Key) (S : ConstraintSystem)
(D : ConstraintDNF)
(hnoBot : ([] : Key) ∉ bounds) (hle : BoundsLe ([] : Key) bounds)
(hk : k = ([] : Key) ∨ k ∈ bounds) (hka : keyAfter k ∈ bounds)
(hcoverS : ∀ c ∈ S, EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds)
(hcoverD : ∀ S' ∈ D, ∀ c ∈ S',
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds) :
searchBad bounds k S D [] = true ↔
∃ bad : List Constraint, bad ∈ choices D ∧
countFeasibleBool bounds k S bad = true := by
constructor
· intro hsearch
obtain ⟨B, -, hhits, hfeas⟩ :=
(searchBad_spec bounds k S D [] hnoBot hle hk hka hcoverS hcoverD (by simp)).mp hsearch
obtain ⟨bad, hbad, hsub⟩ := exists_choices_subset hhits
have hcoverBad : ∀ c ∈ bad,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro c hc
obtain ⟨S', hS', hcS'⟩ := choosesAll_mem (mem_choices.mp hbad) hc
exact hcoverD S' hS' c hcS'
exact ⟨bad, hbad,
(countFeasibleBool_spec bounds k S bad hnoBot hle hcoverS hcoverBad hk hka).mpr
(CountFeasible.mono hsub hfeas)⟩
· rintro ⟨bad, hbad, hfeas⟩
have hchooses : ChoosesAll bad D := mem_choices.mp hbad
have hcoverBad : ∀ c ∈ bad,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro c hc
obtain ⟨S', hS', hcS'⟩ := choosesAll_mem hchooses hc
exact hcoverD S' hS' c hcS'
exact (searchBad_spec bounds k S D [] hnoBot hle hk hka hcoverS hcoverD (by simp)).mpr
⟨bad, by simp, hitsAll_of_choosesAll hchooses,
(countFeasibleBool_spec bounds k S bad hnoBot hle hcoverS hcoverBad hk hka).mp hfeas⟩
/-! ## The lazy oracle and the simple algorithm -/
/-- The lazy exact activity oracle. It has the same decision procedure as
`activeComputable`, but searches for a feasible hitting set instead of
enumerating the full product of one constraint per alternative. -/
def activeComputableFast (r : RangeRead) (res : Result) (k : Key) : Bool :=
let D := characterizingDNF r res
let bounds := activeBounds D k
withinLimitBool r res.keys &&
D.any fun S => searchBad bounds k S D []
/-- The lazy oracle is exact on every readable pair. -/
theorem activeComputableFast_spec {r : RangeRead} {res : Result}
(hread : Readable r res) :
ActiveDecider r res (activeComputableFast r res) := by
intro k
let D := characterizingDNF r res
let bounds := activeBounds D k
have hnoBot : ([] : Key) ∉ bounds := not_mem_activeBounds_bot D k
have hle : BoundsLe ([] : Key) bounds := activeBounds_boundsLe D k
have hcoverD : ∀ S' ∈ D, ∀ c ∈ S',
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro S' hS' c hc
exact dnfEndpointCovered_activeBounds hS' hc
have hk : k = ([] : Key) ∨ k ∈ bounds := by
by_cases hkbot : k = ([] : Key)
· exact Or.inl hkbot
· exact Or.inr (by
rw [mem_activeBounds]
exact Or.inr (Or.inr ⟨hkbot, rfl⟩))
have hka : keyAfter k ∈ bounds := by
rw [mem_activeBounds]
exact Or.inl rfl
rw [activeComputableFast]
rw [Bool.and_eq_true, withinLimitBool_eq, List.any_eq_true]
constructor
· rintro ⟨hw, S, hS, hsearch⟩
obtain ⟨bad, hbad, hfeas⟩ :=
(searchBad_choices bounds k S D hnoBot hle hk hka (hcoverD S hS) hcoverD).mp hsearch
have hchooses : ChoosesAll bad D := mem_choices.mp hbad
have hcoverBad : ∀ c ∈ bad,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro c hc
obtain ⟨S', hS', hcS'⟩ := choosesAll_mem hchooses hc
exact hcoverD S' hS' c hcS'
have hcount : CountFeasible bounds k S bad :=
(countFeasibleBool_spec bounds k S bad hnoBot hle (hcoverD S hS) hcoverBad hk hka).mp
hfeas
exact (flipWitness_iff_exists_counts_canonical (D := D)
(characterizesDNF_characterizingDNF hread)).mpr
⟨hw, S, hS, bad, hchooses, hcount⟩
· intro hw
rcases (flipWitness_iff_exists_counts_canonical (D := D)
(characterizesDNF_characterizingDNF hread)).mp hw with
⟨hwithin, S, hS, bad, hchooses, hcount⟩
refine ⟨hwithin, ⟨S, hS, ?_⟩⟩
have hcoverBad : ∀ c ∈ bad,
EndpointCovered c.lo bounds ∧ EndpointCovered c.hi bounds := by
intro c hc
obtain ⟨S', hS', hcS'⟩ := choosesAll_mem hchooses hc
exact hcoverD S' hS' c hcS'
have hfeas : countFeasibleBool bounds k S bad = true :=
(countFeasibleBool_spec bounds k S bad hnoBot hle (hcoverD S hS) hcoverBad hk hka).mpr
hcount
exact (searchBad_choices bounds k S D hnoBot hle hk hka (hcoverD S hS) hcoverD).mpr
⟨bad, mem_choices.mpr hchooses, hfeas⟩
/-- On a readable pair, the lazy oracle computes exactly the eager oracle's
answer. -/
theorem activeComputableFast_eq {r : RangeRead} {res : Result}
(hread : Readable r res) (k : Key) :
activeComputableFast r res k = activeComputable r res k := by
apply Bool.eq_iff_iff.mpr
rw [activeComputableFast_spec hread k, activeComputable_spec hread k]
end FormalConflictRange