Boolean gates and shared wire operations
DefinitionCNFEncComplexity_RobsonMemoryGatePrimitivescomplexity-theorysatisfiability
Operations on named Boolean wires for the Robson memory circuit, with exact semantics, framing, and polynomial-time compilation from explicit gate descriptions.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonConstraints
import Definitions.Def_CNFEncComplexity_encRobsonIn
import Definitions.Def_CNFEncComplexity_encWords
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_BitString
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Iteration
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_List
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat_Binary
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat_BinaryDiv
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Option
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Encodings_List
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Internal_ResourceFacts
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_TapeLemmas
import Definitions.Def_Complexitylib_0ebd467_Foundations_Data_BitString_Binary
import Definitions.Def_CookLevin_Satisfiability
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.BigOperators.Finprod
import Mathlib.Algebra.BigOperators.Group.List.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Combinatorics.Hall.Finite
import Mathlib.Computability.TuringMachine.Computable
import Mathlib.Data.Fin.Basic
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.Finset.Card
import Mathlib.Data.Fintype.Card
import Mathlib.Data.Fintype.EquivFin
import Mathlib.Data.Fintype.Option
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.List.Basic
import Mathlib.Data.List.Chain
import Mathlib.Data.List.GetD
import Mathlib.Data.List.Nodup
import Mathlib.Data.List.OfFn
import Mathlib.Data.List.Perm.Basic
import Mathlib.Data.List.Sort
import Mathlib.Data.Nat.Bits
import Mathlib.Data.Nat.Digits.Lemmas
import Mathlib.Data.Nat.Size
import Mathlib.Data.Num.Lemmas
import Mathlib.GroupTheory.Perm.Basic
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Logic.Equiv.Prod
import Mathlib.Logic.Function.Basic
import Mathlib.Logic.Function.Iterate
import Mathlib.Tactic.DeriveFintype
import Mathlib.Tactic.FinCases
import Mathlib.Tactic.IntervalCases
import Mathlib.Tactic.Ring
set_option maxHeartbeats 4000000
set_option linter.all false
/- trace primitives -/
/- robson-trace-support -/
namespace CNFEncComplexity.RobsonCNF
open CookLevin
def pinLiteral (out : ℕ) (value : Bool) : Literal :=
if value then .Pos out else .Neg out
/-- The defining clauses for the specified local gate. -/
def Gate.compile : Gate → Formula
| .pin out value => [[pinLiteral out value]]
| .copy out a => [[.Neg out,.Pos a],[.Pos out,.Neg a]]
| .inv out a => [[.Neg out,.Neg a],[.Pos out,.Pos a]]
| .conj out a b => [[.Neg out,.Pos a],[.Neg out,.Pos b],[.Pos out,.Neg a,.Neg b]]
| .disj out a b => [[.Pos out,.Neg a],[.Pos out,.Neg b],[.Neg out,.Pos a,.Pos b]]
| .parity out a b =>
[[.Pos out,.Neg a,.Pos b],[.Pos out,.Pos a,.Neg b],
[.Neg out,.Pos a,.Pos b],[.Neg out,.Neg a,.Neg b]]
| .mux out s a b =>
[[.Neg s,.Neg out,.Pos a],[.Neg s,.Pos out,.Neg a],
[.Pos s,.Neg out,.Pos b],[.Pos s,.Pos out,.Neg b]]
| .assert clause => [clause]
theorem Gate.compile_correct (g : Gate) (α : Assignment) :
Satisfies α g.compile ↔ g.Holds α := by
cases g with
| pin out b =>
cases b <;> cases h : α out <;>
simp [Gate.compile, Gate.Holds, pinLiteral, Satisfies, satisfiesClause, satisfiesLiteral, h]
| copy out a =>
cases h : α out <;> cases ha : α a <;>
simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha]
| inv out a =>
cases h : α out <;> cases ha : α a <;>
simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha]
| conj out a b =>
cases h : α out <;> cases ha : α a <;> cases hb : α b <;>
simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha, hb]
| disj out a b =>
cases h : α out <;> cases ha : α a <;> cases hb : α b <;>
simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha, hb]
| parity out a b =>
cases h : α out <;> cases ha : α a <;> cases hb : α b <;>
simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, ha, hb]
| mux out s a b =>
cases h : α out <;> cases hs : α s <;> cases ha : α a <;> cases hb : α b <;>
simp [Gate.compile, Gate.Holds, Satisfies, satisfiesClause, satisfiesLiteral, h, hs, ha, hb]
| assert clause => simp [Gate.compile, Gate.Holds, Satisfies]
@[simp] theorem Gate.length_compile (g : Gate) : g.compile.length ≤ 4 := by cases g <;> simp [Gate.compile]
def compile (gates : List Gate) : Formula := gates.flatMap Gate.compile
theorem compile_correct (gates : List Gate) (α : Assignment) :
Satisfies α (compile gates) ↔ ∀ g ∈ gates, g.Holds α := by
constructor
· intro h g hg
apply (g.compile_correct α).mp
intro c hc
exact h c (List.mem_flatMap.mpr ⟨g,hg,hc⟩)
· intro h c hc
obtain ⟨g,hg,hc⟩ := List.mem_flatMap.mp hc
exact (g.compile_correct α).mpr (h g hg) c hc
theorem length_compile (gates : List Gate) : (compile gates).length ≤ 4*gates.length := by
induction gates with
| nil => simp [compile]
| cons g gs ih =>
rw [show compile (g::gs) = g.compile ++ compile gs from rfl, List.length_append, List.length_cons]
have h := g.length_compile
omega
/-- The local relation can use arbitrary auxiliary names. Only the projection onto
the specified variables determines the encoded function. -/
theorem isEncoding_of_gates {n : ℕ} (gates : List Gate) (X : Fin n → ℕ)
(f : (Fin n → Bool) → Bool) (hX : Function.Injective X)
(h : ∀ τ, f τ = true ↔ ∃ α : Assignment, (∀ i, α (X i) = τ i) ∧
∀ g ∈ gates, g.Holds α) :
IsEncoding (compile gates) X f := by
refine ⟨hX, fun τ => (h τ).trans ?_⟩
simp only [compile_correct]
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
theorem slotWidth_pos (cost : ℕ) : 0 < slotWidth cost := by
unfold slotWidth
exact Nat.pow_pos (by decide)
theorem le_slotWidth (cost : ℕ) : cost ≤ slotWidth cost := by
cases cost with
| zero => exact Nat.zero_le _
| succ cost =>
simpa [slotWidth,slotLevel,Nat.succ_le_iff] using Nat.lt_size_self cost
theorem slotWidth_le_double {cost : ℕ} (hc : 0 < cost) : slotWidth cost ≤ 2*cost := by
cases h : slotLevel cost with
| zero => simp [slotWidth,h]; omega
| succ j =>
have hj : j < (cost-1).size := by unfold slotLevel at h; omega
have hp : 2^j ≤ cost-1 := Nat.lt_size.mp hj
rw [slotWidth,h,pow_succ]
omega
theorem alignedStart_lower {cursor width : ℕ} (hw : 0 < width) :
cursor ≤ alignedStart cursor width := by
have he := Nat.mod_add_div (cursor+width-1) width
have hm := Nat.mod_lt (cursor+width-1) hw
unfold alignedStart
rw [Nat.mul_comm]
omega
theorem alignedStart_upper {cursor width : ℕ} (hw : 0 < width) :
alignedStart cursor width < cursor+width := by
have hw' := Nat.div_mul_le_self (cursor+width-1) width
unfold alignedStart
omega
theorem dvd_alignedStart (cursor width : ℕ) : width ∣ alignedStart cursor width :=
⟨(cursor+width-1)/width, Nat.mul_comm ..⟩
theorem Starts.length_eq {cursor : ℕ} {costs starts : List ℕ}
(h : Starts cursor costs starts) : starts.length = costs.length := by
induction h with
| nil => rfl
| cons _ _ _ ih => simp [ih]
/-- The greedy schedule rounds each start up to its next aligned slot and uses at most four
units of total time per unit of the original cost, including the idle space. -/
theorem aligned_slots (costs : List ℕ) (hcost : ∀ cost ∈ costs, 0 < cost) (cursor : ℕ) :
∃ starts, Starts cursor costs starts ∧
∀ i : Fin costs.length,
starts[i.val]? = some (starts[i.val]?.getD 0) ∧
(starts[i.val]?.getD 0) + slotWidth costs[i] ≤ cursor+4*costs.sum := by
induction costs generalizing cursor with
| nil =>
exact ⟨[], .nil _, fun i => Fin.elim0 i⟩
| cons cost tail ih =>
let len := slotWidth cost
let start := alignedStart cursor len
have hl : 0 < len := slotWidth_pos cost
have hc : 0 < cost := hcost _ (by simp)
have hs : start + len ≤ cursor + 4*cost := by
have h1 : start < cursor+len := alignedStart_upper hl
have h2 : len ≤ 2*cost := slotWidth_le_double hc
omega
obtain ⟨tl, he, hb⟩ := ih (fun _ h => hcost _ (List.mem_cons_of_mem _ h)) (start+len)
refine ⟨start::tl, .cons (alignedStart_lower hl) (dvd_alignedStart _ _) he,?_⟩
intro i
refine Fin.cases ?_ (fun j => ?_) i
· simp only [Fin.val_zero, List.getElem?_cons_zero, Option.getD_some, List.getElem_cons_zero,
List.sum_cons, true_and]
exact hs.trans (by omega)
· obtain ⟨hj, hk⟩ := hb j
change tl[j.val]? = some (tl[j.val]?.getD 0) ∧
tl[j.val]?.getD 0 + slotWidth tail[j] ≤ cursor+4*(cost+tail.sum)
exact ⟨hj,by omega⟩
/-- One level has budget exactly two to the power of the height. -/
theorem level_capacity {level height : ℕ} (h : level ≤ height) :
2^(height-level) * 2^level = (2:ℕ)^height := by
rw [← pow_add, Nat.sub_add_cancel h]
theorem allocated_bit_budget (height : ℕ) :
((List.range (height+1)).map (fun j => 2^(height-j)*2^j)).sum =
(height+1)*2^height := by
calc
_ = ((List.range (height+1)).map (fun _ => (2:ℕ)^height)).sum := by
congr 1
apply List.map_congr_left
intro j hj
exact level_capacity (by have h := List.mem_range.mp hj; omega)
_ = _ := by simp
/-- The dyadic horizon is linear in the original time bound. All slots from the greedy
schedule can be put in this horizon at levels of at most its height. -/
theorem compact_schedule (costs : List ℕ) (hc : ∀ c ∈ costs, 0 < c)
{t : ℕ} (ht : costs.sum ≤ t) :
let H := slotLevel (4*(t+1))
2^H ≤ 8*(t+1) ∧
∃ starts, Starts 0 costs starts ∧ ∀ i : Fin costs.length,
slotLevel costs[i] ≤ H ∧
∃ j : Fin (2^(H-slotLevel costs[i])),
starts[i.val]? = some (j.val*slotWidth costs[i]) := by
intro H
have hH : 2^H ≤ 8*(t+1) := by
have h := slotWidth_le_double (cost := 4*(t+1)) (by omega)
simpa only [H,slotWidth,← Nat.mul_assoc] using h
refine ⟨hH,?_⟩
obtain ⟨starts, hstarts, hg⟩ := aligned_slots costs hc 0
refine ⟨starts,hstarts,?_⟩
have allAlign {cursor : ℕ} {costs starts : List ℕ} (h : Starts cursor costs starts) :
∀ i : Fin costs.length, slotWidth costs[i] ∣ (starts[i.val]?.getD 0) := by
induction h with
| nil => intro i; exact Fin.elim0 i
| @cons cursor cost start costs starts _ hdiv _ ih =>
intro i
refine Fin.cases ?_ (fun i => ?_) i
· simpa using hdiv
· simpa using ih i
intro i
obtain ⟨j,hj⟩ := allAlign hstarts i
have hTime := (hg i).2
have hHor : 4*(t+1) ≤ (2:ℕ)^H := le_slotWidth _
have hWidth : slotWidth costs[i] ≤ (2:ℕ)^H := by omega
have hLev : slotLevel costs[i] ≤ H :=
(Nat.pow_le_pow_iff_right (by decide)).mp hWidth
have hjlt : j < 2^(H-slotLevel costs[i]) := by
by_contra! hge
have hm := Nat.mul_le_mul_right (slotWidth costs[i]) hge
rw [show 2^(H-slotLevel costs[i]) * slotWidth costs[i] = 2^H from level_capacity hLev,
Nat.mul_comm j, ← hj] at hm
omega
refine ⟨hLev,⟨j,hjlt⟩,?_⟩
rw [Nat.mul_comm,← hj]
exact (hg i).1
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
private def rank (t : ℕ) (s : ℕ × ℕ) : ℕ := s.1*(layoutHeight t+1)+s.2
theorem layout_mem {t a j : ℕ} :
(a,j) ∈ layoutSlots t ↔ a < layoutHorizon t ∧ j ≤ layoutHeight t ∧ a % 2^j = 0 := by
simp [layoutSlots,List.mem_flatMap,List.mem_map,List.mem_filter,List.mem_range] <;> omega
theorem layout_sorted (t : ℕ) : (layoutSlots t).Pairwise (fun s s' => rank t s < rank t s') := by
unfold layoutSlots
rw [List.pairwise_flatMap]
constructor
· intro a ha
have hp : (List.range (layoutHeight t+1)).Pairwise (·<·) := List.pairwise_lt_range
apply (hp.filter (fun j => a % 2^j = 0)).map (fun j => (a,j))
intro u v hh
exact Nat.add_lt_add_left hh _
· apply (List.pairwise_lt_range).imp
intro a b hab x hx y hy
obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hx
obtain ⟨k,hk,rfl⟩ := List.mem_map.mp hy
have hdj := List.mem_range.mp (List.mem_filter.mp hj).1
have hb : (a+1)*(layoutHeight t+1) ≤ b*(layoutHeight t+1) :=
Nat.mul_le_mul_right _ hab
simp only [rank,Prod.fst,Prod.snd]
rw [Nat.add_mul,Nat.one_mul] at hb
omega
theorem layout_nodup (t : ℕ) : (layoutSlots t).Nodup :=
(layout_sorted t).imp (fun h he => (Nat.ne_of_lt h) (congrArg _ he))
/-- Dyadic starts are strictly chronological, independent of the idle gaps. -/
theorem Starts.ordered {cursor : ℕ} {costs starts : List ℕ} (h : Starts cursor costs starts) :
starts.Pairwise (·<·) ∧ ∀ a ∈ starts, cursor ≤ a := by
induction h with
| nil => simp
| @cons cursor cost start costs starts hs _ _ ih =>
refine ⟨List.pairwise_cons.mpr ⟨?_,ih.1⟩,?_⟩
· intro a ha
have h := ih.2 a ha
have h' := slotWidth_pos cost
omega
· intro a ha
rcases List.mem_cons.mp ha with rfl | ha
· exact hs
· exact hs.trans ((Nat.le_add_right _ _).trans (ih.2 a ha))
/-- Serial bit names are the product embedding of the naturally bounded port indices. -/
def portIndex (n t : ℕ) :
(Fin n ⊕ ((Fin (layoutHorizon t) × Fin (layoutHeight t+1)) × Fin 19) ×
Fin (layoutHorizon t)) ≃ Fin (sharedLimit n t) :=
(Equiv.sumCongr (Equiv.refl _)
((((finProdFinEquiv.prodCongr (Equiv.refl (Fin 19))).trans finProdFinEquiv).prodCongr
(Equiv.refl (Fin (layoutHorizon t)))).trans finProdFinEquiv)).trans finSumFinEquiv
theorem portIndex_input {n t : ℕ} (i : Fin n) :
(portIndex n t (.inl i)).val = i.val := rfl
theorem portIndex_other {n t : ℕ} (a : Fin (layoutHorizon t))
(j : Fin (layoutHeight t+1)) (f : Fin 19) (b : Fin (layoutHorizon t)) :
(portIndex n t (.inr (((a,j),f),b))).val = port n t (a,j) f.val b.val := by
change n+(b.val+layoutHorizon t*(f.val+19*(j.val+(layoutHeight t+1)*a.val))) = _
unfold port
simp only [Prod.fst,Prod.snd]
ring
theorem port_lt_shared {n t a j f b : ℕ} (ha : a < layoutHorizon t)
(hj : j ≤ layoutHeight t) (hf : f < 19) (hb : b < layoutHorizon t) :
port n t (a,j) f b < sharedLimit n t := by
rw [← portIndex_other ⟨a,ha⟩ ⟨j,by omega⟩ ⟨f,hf⟩ ⟨b,hb⟩]
exact Fin.isLt _
theorem ports_agree {α β : Assignment} {n t : ℕ}
(h : ∀ r < sharedLimit n t, α r = β r) :
readStream α n t = readStream β n t ∧ memoryStream α n t = memoryStream β n t ∧
inputTape α n = inputTape β n := by
have hGet {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {f b : ℕ} (hf : f < 19) (hb : b < 2^s.2) :
α (port n t s f b) = β (port n t s f b) := by
rcases s with ⟨a,j⟩
obtain ⟨ha,hj,_⟩ := layout_mem.mp hs
exact h _ (port_lt_shared ha hj hf (hb.trans_le (Nat.pow_le_pow_right (by decide) hj)))
have hW {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {f : ℕ} (hf : f < 19) :
portWord α n t s f = portWord β n t s f := by
unfold portWord
congr 1
apply List.map_congr_left
intro b hb
rw [hGet hs hf (List.mem_range.mp hb)]
refine ⟨?_,?_,?_⟩
· unfold readStream
apply List.filterMap_congr
intro s hs
have hP : 0 < 2^s.2 := Nat.pow_pos (by decide)
unfold portInput
rw [hGet hs (by decide : 0 < 19) hP,hGet hs (by decide : 1 < 19) hP,
hGet hs (by decide : 2 < 19) hP]
· unfold memoryStream
apply List.flatMap_congr
intro s hs
apply List.filterMap_congr
intro i hi
have hi3 := List.mem_range.mp hi
have hP : 0 < 2^s.2 := Nat.pow_pos (by decide)
dsimp only [portMemory]
rw [hGet hs (by omega : 3+5*i < 19) hP,hGet hs (by omega : 3+5*i+1 < 19) hP,
hW hs (by omega : 3+5*i+2 < 19),hW hs (by omega : 3+5*i+3 < 19),
hW hs (by omega : 3+5*i+4 < 19)]
· apply congrArg List.ofFn
funext i
exact h _ (i.isLt.trans_le (Nat.le_add_right _ _))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
theorem gate_congr {α β : Assignment} (g : Gate) (h : ∀ r ∈ Gate.names g, α r = β r) :
g.Holds α ↔ g.Holds β := by
cases g with
| pin a =>
simp only [Gate.names,List.mem_singleton,forall_eq] at h
simp only [Gate.Holds,h]
| copy a b | inv a b =>
rw [Gate.Holds,Gate.Holds,h a (by simp [Gate.names]),h b (by simp [Gate.names])]
| conj a b c | disj a b c | parity a b c =>
rw [Gate.Holds,Gate.Holds,h a (by simp [Gate.names]),h b (by simp [Gate.names]),
h c (by simp [Gate.names])]
| mux a b c d =>
rw [Gate.Holds,Gate.Holds,h a (by simp [Gate.names]),h b (by simp [Gate.names]),
h c (by simp [Gate.names]),h d (by simp [Gate.names])]
| assert ls =>
change ls.any (satisfiesLiteral α) = true ↔ ls.any (satisfiesLiteral β) = true
have hx : ∀ lit ∈ ls, satisfiesLiteral α lit = satisfiesLiteral β lit := by
intro lit hl
have hh := h lit.var (List.mem_map.mpr ⟨lit,hl,rfl⟩)
cases lit <;> simp_all [satisfiesLiteral,Literal.var]
have he : List.any ls (satisfiesLiteral α) = List.any ls (satisfiesLiteral β) := by
clear h
induction ls with
| nil => rfl
| cons l ls ih =>
simp only [List.any_cons]
rw [hx l (by simp),ih (fun x hx' => hx x (by simp [hx']))]
rw [he]
theorem simultaneous_extensions (base : ℕ) (gates : Fin 3 → List Gate) (α : Assignment)
(ht : ∀ i, ∀ g ∈ gates i, ∀ r ∈ Gate.names g, owns base i r)
(he : ∀ i, ExtendsWith base (gates i) α) :
ExtendsWith base (gates 0 ++ gates 1 ++ gates 2) α := by
classical
choose β hβ hGate using he
let f (r : ℕ) : Fin 3 := ⟨(r-base)%3,Nat.mod_lt _ (by decide)⟩
let after (r : ℕ) := if r < base then α r else β (f r) r
have hb (i : Fin 3) (r : ℕ) (hr : owns base i r) : after r = β i r := by
by_cases h : r < base
· simp [after,h,hβ i r h]
· have hf : f r = i := Fin.ext (hr.resolve_left h)
simp [after,h,hf]
refine ⟨after,fun r hr => by simp [after,hr],?_⟩
intro g hg
simp only [List.mem_append] at hg
rcases hg with (hg|hg)|hg
· exact (gate_congr g (fun r hr => hb 0 r (ht _ _ hg _ hr))).mpr (hGate _ _ hg)
· exact (gate_congr g (fun r hr => hb 1 r (ht _ _ hg _ hr))).mpr (hGate _ _ hg)
· exact (gate_congr g (fun r hr => hb 2 r (ht _ _ hg _ hr))).mpr (hGate _ _ hg)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
def slotCenter (s : ℕ × ℕ) : ℕ := 2*s.1+2^s.2
private theorem alignedCenter_multiple {a j : ℕ} (ha : a % 2^j = 0) :
slotCenter (a,j) = (2*(a / 2^j)+1)*2^j := by
have ha' := Nat.mod_add_div a (2^j)
rw [ha,Nat.zero_add] at ha'
unfold slotCenter
dsimp
rw [Nat.add_mul,Nat.one_mul, Nat.mul_assoc,Nat.mul_comm (a/2^j),ha']
private theorem alignedCenter_val {a j : ℕ} (ha : a % 2^j = 0) :
slotCenter (a,j) % 2^(j+1) = 2^j := by
rw [alignedCenter_multiple ha,Nat.pow_succ,Nat.add_mul,Nat.one_mul]
rw [show 2*(a/2^j)*2^j = (a/2^j)*(2^j*2) by ring,Nat.mul_add_mod_self_right]
have hj : 0 < 2^j := Nat.pow_pos (by decide)
exact Nat.mod_eq_of_lt (by omega)
private theorem alignedCenter_dvd {a j : ℕ} (ha : a % 2^j = 0) :
2^j ∣ slotCenter (a,j) := by
rw [alignedCenter_multiple ha]
exact Nat.dvd_mul_left _ _
theorem slotCenter_injOn (t : ℕ) {s r : ℕ × ℕ}
(hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (he : slotCenter s = slotCenter r) : s=r := by
rcases s with ⟨a,j⟩
rcases r with ⟨b,k⟩
have ha := (layout_mem.mp hs).2.2
have hb := (layout_mem.mp hr).2.2
have hNoLt {a b j k : ℕ} (ha : a % 2^j = 0) (hb : b % 2^k = 0)
(he : slotCenter (a,j) = slotCenter (b,k)) : ¬ j < k := by
intro hLt
have hd : 2^(j+1) ∣ 2^k := Nat.pow_dvd_pow 2 hLt
have hh := dvd_trans hd (alignedCenter_dvd hb)
rw [← he, Nat.dvd_iff_mod_eq_zero, alignedCenter_val ha] at hh
exact Nat.ne_of_gt (Nat.pow_pos (by decide)) hh
have heJ : j=k := by
apply Nat.le_antisymm (Nat.le_of_not_gt (hNoLt hb ha he.symm))
exact Nat.le_of_not_gt (hNoLt ha hb he)
subst k
unfold slotCenter at he
dsimp at he
have : a=b := by omega
simp [this]
theorem slotCenter_lt (t : ℕ) {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) :
slotCenter s < 2*layoutHorizon t := by
rcases s with ⟨a,j⟩
obtain ⟨ha,hj,hDiv⟩ := layout_mem.mp hs
have hd : 2^j ∣ layoutHorizon t := Nat.pow_dvd_pow 2 hj
obtain ⟨r,hr⟩ := hd
have hEq := Nat.mod_add_div a (2^j)
rw [hDiv,Nat.zero_add] at hEq
have hQ : a/2^j < r := by
apply Nat.lt_of_mul_lt_mul_left (a := 2^j)
rw [hEq,← hr]
exact ha
have hCap : a + 2^j ≤ layoutHorizon t := by
have hh := Nat.mul_le_mul_left (2^j) hQ
rw [Nat.succ_eq_add_one,Nat.mul_add,Nat.mul_one,hEq,← hr] at hh
exact hh
have hP : 0 < 2^j := Nat.pow_pos (by decide)
unfold slotCenter
dsimp
omega
theorem layoutSlots_length_le (t : ℕ) : (layoutSlots t).length ≤ 2*layoutHorizon t := by
let l := (layoutSlots t).map slotCenter
have hND : l.Nodup := by
apply List.Nodup.map_on _ (layout_nodup t)
exact fun _ hs _ hr he => slotCenter_injOn t hs hr he
have hSub : l ⊆ List.range (2*layoutHorizon t) := by
intro m hm
obtain ⟨s,hs,rfl⟩ := List.mem_map.mp hm
exact List.mem_range.mpr (slotCenter_lt t hs)
have h := hND.length_le_of_subset hSub
simpa [l] using h
end CNFEncComplexity.Robson
namespace CNFEncComplexity.RobsonCNF
open CookLevin
/-- The current less-than and equality bits occupy the first two wires of each group.
The other two wires test the current input bit pair, if present. -/
def ltWire (base i : ℕ) := base + 4*i
def eqWire (base i : ℕ) := base + 4*i + 1
def diffWire (base i : ℕ) := base + 4*i + 2
def sameWire (base i : ℕ) := base + 4*i + 3
def compareStep (base i : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
[.parity (diffWire base i) (lhs i) (rhs i),
.inv (sameWire base i) (diffWire base i),
.mux (ltWire base (i+1)) (diffWire base i) (rhs i) (ltWire base i),
.conj (eqWire base (i+1)) (sameWire base i) (eqWire base i)]
/-- Four gates per bit over a little-endian key, plus initial less-than and equal bits. -/
def compareCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
[.pin (ltWire base 0) false, .pin (eqWire base 0) true] ++
(List.range n).flatMap (fun i => compareStep base i lhs rhs)
theorem length_compareCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) :
(compareCircuit base n lhs rhs).length = 4*n+2 := by
have h (xs : List ℕ) : (xs.flatMap (fun i => compareStep base i lhs rhs)).length = 4*xs.length := by
induction xs with
| nil => rfl
| cons i xs ih =>
simp only [List.flatMap_cons, List.length_append, List.length_cons, ih]
change 4+4*xs.length = 4*(xs.length+1)
omega
simp only [compareCircuit, List.length_append, List.length_cons, List.length_nil, h, List.length_range]
omega
/-- Numeric value of the indicated prefix, little-endian. -/
def wireValue (α : Assignment) (key : ℕ → ℕ) : ℕ → ℕ
| 0 => 0
| n+1 => wireValue α key n + (if α (key n) then 2^n else 0)
theorem wireValue_lt (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
wireValue α key n < 2^n := by
induction n with
| zero => simp [wireValue]
| succ n ih =>
simp only [wireValue, pow_succ]
split <;> omega
theorem wireValue_congr {α β : Assignment} {key : ℕ → ℕ} {n : ℕ}
(h : ∀ i < n, α (key i) = β (key i)) :
wireValue α key n = wireValue β key n := by
induction n with
| zero => rfl
| succ n ih =>
rw [wireValue, wireValue, ih (fun i hi => h i (by omega)), h n (by omega)]
theorem wireValue_lt_succ (α : Assignment) (lhs rhs : ℕ → ℕ) (i : ℕ) :
decide (wireValue α lhs (i+1) < wireValue α rhs (i+1)) =
if α (lhs i) ^^ α (rhs i) then α (rhs i) else decide (wireValue α lhs i < wireValue α rhs i) := by
have hL := wireValue_lt α lhs i
have hR := wireValue_lt α rhs i
cases hl : α (lhs i) <;> cases hr : α (rhs i)
· simp [wireValue, hl, hr]
· simp [wireValue, hl, hr]
omega
· simp [wireValue, hl, hr]
omega
· simp [wireValue, hl, hr]
theorem wireValue_eq_succ (α : Assignment) (lhs rhs : ℕ → ℕ) (i : ℕ) :
decide (wireValue α lhs (i+1) = wireValue α rhs (i+1)) =
((!(α (lhs i) ^^ α (rhs i))) && decide (wireValue α lhs i = wireValue α rhs i)) := by
have hL := wireValue_lt α lhs i
have hR := wireValue_lt α rhs i
cases hl : α (lhs i) <;> cases hr : α (rhs i)
· simp [wireValue, hl, hr]
· simp [wireValue, hl, hr]
omega
· simp [wireValue, hl, hr]
omega
· simp [wireValue, hl, hr]
theorem compareCircuit_outputs (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ compareCircuit base n lhs rhs, g.Holds α) :
∀ i ≤ n,
α (ltWire base i) = decide (wireValue α lhs i < wireValue α rhs i) ∧
α (eqWire base i) = decide (wireValue α lhs i = wireValue α rhs i) := by
intro i hi
induction i with
| zero =>
have hl := h (.pin (ltWire base 0) false) (by simp [compareCircuit])
have he := h (.pin (eqWire base 0) true) (by simp [compareCircuit])
exact ⟨hl,he⟩
| succ i ih =>
obtain ⟨hL,hE⟩ := ih (by omega)
have hh : ∀ g ∈ compareStep base i lhs rhs, g.Holds α := by
intro g hg
exact h g (List.mem_append.mpr (Or.inr (List.mem_flatMap.mpr
⟨i,List.mem_range.mpr (by omega),hg⟩)))
have hD : α (diffWire base i) = (α (lhs i) ^^ α (rhs i)) :=
hh (.parity (diffWire base i) (lhs i) (rhs i)) (by simp [compareStep])
have hS : α (sameWire base i) = !α (diffWire base i) :=
hh (.inv (sameWire base i) (diffWire base i)) (by simp [compareStep])
have hL' : α (ltWire base (i+1)) =
if α (diffWire base i) then α (rhs i) else α (ltWire base i) :=
hh (.mux (ltWire base (i+1)) (diffWire base i) (rhs i) (ltWire base i)) (by simp [compareStep])
have hE' : α (eqWire base (i+1)) = (α (sameWire base i) && α (eqWire base i)) :=
hh (.conj (eqWire base (i+1)) (sameWire base i) (eqWire base i)) (by simp [compareStep])
exact ⟨by rw [hL',hD,hL,wireValue_lt_succ], by rw [hE',hS,hD,hE,wireValue_eq_succ]⟩
/-- Canonical extension of an assignment after introducing comparator wires. -/
def compareAssign (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (k : ℕ) : Bool :=
if k < base then α k else
let i := (k-base)/4
match (k-base)%4 with
| 0 => decide (wireValue α lhs i < wireValue α rhs i)
| 1 => decide (wireValue α lhs i = wireValue α rhs i)
| 2 => α (lhs i) ^^ α (rhs i)
| _ => !(α (lhs i) ^^ α (rhs i))
theorem compareAssign_preserves {base k : ℕ} (hk : k < base)
(lhs rhs : ℕ → ℕ) (α : Assignment) :
compareAssign base lhs rhs α k = α k := by simp [compareAssign,hk]
private theorem wire_divMod (base i j : ℕ) (hj : j < 4) :
¬base+4*i+j < base ∧ (base+4*i+j-base)/4 = i ∧ (base+4*i+j-base)%4 = j := by
omega
@[simp] theorem compareAssign_lt (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
compareAssign base lhs rhs α (ltWire base i) =
decide (wireValue α lhs i < wireValue α rhs i) := by
obtain ⟨h,hD,hM⟩ := wire_divMod base i 0 (by decide)
simp only [Nat.add_zero] at h hD hM
simp [compareAssign,ltWire,h,hD,hM]
@[simp] theorem compareAssign_eq (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
compareAssign base lhs rhs α (eqWire base i) =
decide (wireValue α lhs i = wireValue α rhs i) := by
obtain ⟨h,hD,hM⟩ := wire_divMod base i 1 (by decide)
simp [compareAssign,eqWire,h,hD,hM]
@[simp] theorem compareAssign_diff (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
compareAssign base lhs rhs α (diffWire base i) = (α (lhs i) ^^ α (rhs i)) := by
obtain ⟨h,hD,hM⟩ := wire_divMod base i 2 (by decide)
simp [compareAssign,diffWire,h,hD,hM]
@[simp] theorem compareAssign_same (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (i : ℕ) :
compareAssign base lhs rhs α (sameWire base i) = !(α (lhs i) ^^ α (rhs i)) := by
obtain ⟨h,hD,hM⟩ := wire_divMod base i 3 (by decide)
simp [compareAssign,sameWire,h,hD,hM]
theorem compareCircuit_extends (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∀ g ∈ compareCircuit base n lhs rhs, g.Holds (compareAssign base lhs rhs α) := by
intro g hg
rcases List.mem_append.mp hg with h | h
· rcases List.mem_cons.mp h with hg | h
· subst g
simp [Gate.Holds,wireValue]
· have hg : g = Gate.pin (eqWire base 0) true := by simpa using h
subst g
simp [Gate.Holds,wireValue]
· obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp h
have hi' := List.mem_range.mp hi
simp only [compareStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl | rfl | rfl | rfl <;>
simp [Gate.Holds, compareAssign_preserves (hL i hi'), compareAssign_preserves (hR i hi'),
wireValue_lt_succ, wireValue_eq_succ]
/-- Correctness and realizability for one comparator in Cook–Levin's formula format. -/
theorem compareFormula_exact (base n : ℕ) (lhs rhs : ℕ → ℕ)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base)
(α : Assignment) (lb eb : Bool) :
(∃ β : Assignment, (∀ k < base, β k = α k) ∧
Satisfies β (compile (compareCircuit base n lhs rhs)) ∧
β (ltWire base n) = lb ∧ β (eqWire base n) = eb) ↔
lb = decide (wireValue α lhs n < wireValue α rhs n) ∧
eb = decide (wireValue α lhs n = wireValue α rhs n) := by
constructor
· rintro ⟨β,hβ,hSat,hl,he⟩
obtain ⟨hLt,hEq⟩ := compareCircuit_outputs base n lhs rhs β ((compile_correct _ _).mp hSat) n le_rfl
have hlv := wireValue_congr (α := β) (β := α) (fun i hi => hβ (lhs i) (hL i hi))
have hrv := wireValue_congr (α := β) (β := α) (fun i hi => hβ (rhs i) (hR i hi))
rw [hlv,hrv] at hLt hEq
exact ⟨hl.symm.trans hLt, he.symm.trans hEq⟩
· intro ⟨hl,he⟩
refine ⟨compareAssign base lhs rhs α, fun k hk => compareAssign_preserves hk _ _ _,
(compile_correct _ _).mpr (compareCircuit_extends base n lhs rhs α hL hR), ?_, ?_⟩
· simpa using hl.symm
· simpa using he.symm
/-- Join two little-endian subkeys, with the first subkey less significant. -/
def joinKey (low high : ℕ → ℕ) (n : ℕ) (i : ℕ) : ℕ :=
if i < n then low i else high (i-n)
theorem wireValue_key_congr (α : Assignment) {lhs rhs : ℕ → ℕ} {n : ℕ}
(h : ∀ i < n, lhs i = rhs i) :
wireValue α lhs n = wireValue α rhs n := by
induction n with
| zero => rfl
| succ n ih =>
rw [wireValue,wireValue,ih (fun i hi => h i (by omega)),h n (by omega)]
theorem wireValue_joinKey (α : Assignment) (low high : ℕ → ℕ) (n m : ℕ) :
wireValue α (joinKey low high n) (n+m) =
wireValue α low n + 2^n * wireValue α high m := by
induction m with
| zero =>
rw [Nat.add_zero,wireValue,Nat.mul_zero,Nat.add_zero]
apply wireValue_key_congr
intro i hi
rw [joinKey,if_pos hi]
| succ m ih =>
have hJ : joinKey low high n (n+m) = high m := by
rw [joinKey,if_neg (by omega)]
simp
change wireValue α (joinKey low high n) (n+m) + (if α (joinKey low high n (n+m))
then 2^(n+m) else 0) = wireValue α low n +
2^n * (wireValue α high m + if α (high m) then 2^m else 0)
rw [ih,hJ,Nat.mul_add,pow_add]
cases h : α (high m) <;> simp [h,Nat.add_assoc]
/-- Stable memory order compares address first and preserves the chronological order
of records at a common address. The timestamp is the low block. -/
theorem wireValue_joinKey_lt (α : Assignment)
(timeL timeR addrL addrR : ℕ → ℕ) (tW aW : ℕ) :
wireValue α (joinKey timeL addrL tW) (tW+aW) <
wireValue α (joinKey timeR addrR tW) (tW+aW) ↔
wireValue α addrL aW < wireValue α addrR aW ∨
(wireValue α addrL aW = wireValue α addrR aW ∧
wireValue α timeL tW < wireValue α timeR tW) := by
rw [wireValue_joinKey,wireValue_joinKey]
let b : ℕ := 2^tW
let al := wireValue α addrL aW
let ar := wireValue α addrR aW
let tl := wireValue α timeL tW
let tr := wireValue α timeR tW
change tl+b*al < tr+b*ar ↔ al < ar ∨ (al=ar ∧ tl < tr)
have htL : tl < b := wireValue_lt _ _ _
have htR : tr < b := wireValue_lt _ _ _
have hLess (x y : ℕ) (hx : x < y) : b*x+b ≤ b*y := by
rw [← Nat.mul_succ]
exact Nat.mul_le_mul_left _ hx
rcases lt_trichotomy al ar with hA | hA | hA
· have hh := hLess al ar hA
exact ⟨fun _ => Or.inl hA,fun _ => by omega⟩
· rw [hA]
simp
· have hh := hLess ar al hA
exact ⟨fun h => by omega,fun h => by omega⟩
/-- Names read and written by a gate. This allows independently allocated comparators
to be combined under a single assignment. -/
def Gate.names : Gate → List ℕ
| .pin out _ => [out]
| .copy out a => [out,a]
| .inv out a => [out,a]
| .conj out a b | .disj out a b | .parity out a b => [out,a,b]
| .mux out s a b => [out,s,a,b]
| .assert c => c.map Literal.var
theorem Gate.holds_congr (g : Gate) (α β : Assignment)
(h : ∀ i ∈ g.names, α i = β i) :
g.Holds α ↔ g.Holds β := by
cases g with
| pin out v => simp [Gate.names,Gate.Holds] at h ⊢; rw [h]
| copy out a => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2]
| inv out a => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2]
| conj out a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2]
| disj out a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2]
| parity out a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2]
| mux out s a b => simp [Gate.names,Gate.Holds] at h ⊢; rw [h.1,h.2.1,h.2.2.1,h.2.2.2]
| assert c =>
change (satisfiesClause α c = true) ↔ (satisfiesClause β c = true)
rw [satisfiesClause_congr (fun l hl => h l.var (List.mem_map.mpr ⟨l,hl,rfl⟩))]
theorem compareCircuit_names_lt (base n : ℕ) (lhs rhs : ℕ → ℕ)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∀ g ∈ compareCircuit base n lhs rhs, ∀ k ∈ g.names, k < base+4*n+2 := by
intro g hg k hk
rcases List.mem_append.mp hg with hg | hg
· simp only [List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl | rfl <;>
simp [Gate.names,ltWire,eqWire] at hk <;> omega
· obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp hg
have hi' := List.mem_range.mp hi
have hli := hL i hi'
have hri := hR i hi'
simp only [compareStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl | rfl | rfl | rfl <;>
simp [Gate.names,ltWire,eqWire,diffWire,sameWire] at hk <;> omega
/-- A comparator assignment need only change its own interval of fresh names. -/
theorem compareCircuit_extends_interval (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∃ β : Assignment,
(∀ k, (k < base ∨ base+4*n+2 ≤ k) → β k = α k) ∧
(∀ g ∈ compareCircuit base n lhs rhs, g.Holds β) := by
let β : Assignment := fun k => if k < base+4*n+2 then compareAssign base lhs rhs α k else α k
refine ⟨β, ?_, ?_⟩
· intro k hk
rcases hk with hk | hk
· simp [β, show k < base+4*n+2 by omega, compareAssign_preserves hk]
· simp [β, Nat.not_lt_of_ge hk]
· intro g hg
apply (g.holds_congr (compareAssign base lhs rhs α) β (fun k hk => by
simp [β,compareCircuit_names_lt base n lhs rhs hL hR g hg k hk])).mp
exact compareCircuit_extends base n lhs rhs α hL hR g hg
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open CookLevin
/-- A carry or borrow takes the first wire of each eight-wire region. -/
def rippleCarryWire (base i : ℕ) := base+8*i
def rippleXorWire (base i : ℕ) := base+8*i+1
def rippleBitWire (base i : ℕ) := base+8*i+2
private def invLeftWire (base i : ℕ) := base+8*i+3
private def invXorWire (base i : ℕ) := base+8*i+4
private def firstCarryWire (base i : ℕ) := base+8*i+5
private def secondCarryWire (base i : ℕ) := base+8*i+6
/-- Successor carry for ordinary addition, or successor borrow for subtraction. -/
def rippleNext (subtract a b carry : Bool) : Bool :=
if subtract then ((!a && b) || (!(a ^^ b) && carry))
else ((a && b) || ((a ^^ b) && carry))
def rippleStep (subtract : Bool) (base i : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
let a := lhs i
let b := rhs i
let p := rippleXorWire base i
let c := rippleCarryWire base i
let changeA := invLeftWire base i
let changeP := invXorWire base i
let c₁ := firstCarryWire base i
let c₂ := secondCarryWire base i
[.parity p a b,
.parity (rippleBitWire base i) p c,
.inv changeA a,
.inv changeP p,
.conj c₁ (if subtract then changeA else a) b,
.conj c₂ (if subtract then changeP else p) c,
.disj (rippleCarryWire base (i+1)) c₁ c₂]
def rippleCircuit (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
.pin (rippleCarryWire base 0) false ::
(List.range n).flatMap (fun i => rippleStep subtract base i lhs rhs)
theorem length_rippleCircuit (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ) :
(rippleCircuit subtract base n lhs rhs).length = 7*n+1 := by
have h (xs : List ℕ) :
(xs.flatMap (fun i => rippleStep subtract base i lhs rhs)).length = 7*xs.length := by
induction xs with
| nil => rfl
| cons i xs ih =>
simp only [List.flatMap_cons,List.length_append,List.length_cons,ih]
change 7+7*xs.length = 7*(xs.length+1)
omega
simp only [rippleCircuit,List.length_cons,h,List.length_range]
theorem rippleStep_outputs (subtract : Bool) (base i : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (h : ∀ g ∈ rippleStep subtract base i lhs rhs, g.Holds α) :
α (rippleBitWire base i) = ((α (lhs i) ^^ α (rhs i)) ^^ α (rippleCarryWire base i)) ∧
α (rippleCarryWire base (i+1)) =
rippleNext subtract (α (lhs i)) (α (rhs i)) (α (rippleCarryWire base i)) := by
let p := rippleXorWire base i
let c := rippleCarryWire base i
let changeA := invLeftWire base i
let changeP := invXorWire base i
let c₁ := firstCarryWire base i
let c₂ := secondCarryWire base i
have hp : α p = (α (lhs i) ^^ α (rhs i)) :=
h (.parity p (lhs i) (rhs i)) (by simp [rippleStep,p])
have hbit : α (rippleBitWire base i) = (α p ^^ α c) :=
h (.parity (rippleBitWire base i) p c) (by simp [rippleStep,p,c])
have ha : α changeA = !α (lhs i) :=
h (.inv changeA (lhs i)) (by simp [rippleStep,changeA])
have hcp : α changeP = !α p :=
h (.inv changeP p) (by simp [rippleStep,changeP,p])
have h1 : α c₁ = (α (if subtract then changeA else lhs i) && α (rhs i)) :=
h (.conj c₁ (if subtract then changeA else lhs i) (rhs i)) (by simp [rippleStep,c₁,changeA])
have h2 : α c₂ = (α (if subtract then changeP else p) && α c) :=
h (.conj c₂ (if subtract then changeP else p) c) (by simp [rippleStep,c₂,changeP,p,c])
have hc : α (rippleCarryWire base (i+1)) = (α c₁ || α c₂) :=
h (.disj (rippleCarryWire base (i+1)) c₁ c₂) (by simp [rippleStep,c₁,c₂])
exact ⟨by rw [hbit,hp],by cases subtract <;> simp [rippleNext,hc,h1,h2,ha,hcp,hp,c]⟩
private theorem wireValue_succ_bit (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
wireValue α key (n+1) = wireValue α key n + (α (key n)).toNat * 2^n := by
cases h : α (key n) <;> simp [wireValue,h]
/-- The recursive value used by the arithmetic gadgets agrees with the weighted
sum on numeric-address ports. -/
theorem wireValue_eq_sum (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
wireValue α key n =
((List.range n).map fun i => (α (key i)).toNat * 2^i).sum := by
induction n with
| zero => rfl
| succ n ih =>
rw [wireValue_succ_bit,ih,List.range_succ,List.map_append,List.sum_append]
simp
private theorem add_bit_equation (a b c : Bool) :
a.toNat + b.toNat + c.toNat = ((a ^^ b) ^^ c).toNat + 2*(rippleNext false a b c).toNat := by
cases a <;> cases b <;> cases c <;> decide
private theorem subtract_bit_equation (a b c : Bool) :
a.toNat + 2*(rippleNext true a b c).toNat = b.toNat + c.toNat + ((a ^^ b) ^^ c).toNat := by
cases a <;> cases b <;> cases c <;> decide
theorem rippleCircuit_add (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ rippleCircuit false base n lhs rhs, g.Holds α) :
∀ i ≤ n, wireValue α lhs i + wireValue α rhs i =
wireValue α (rippleBitWire base) i + (α (rippleCarryWire base i)).toNat * 2^i := by
intro i hi
induction i with
| zero =>
have hc : α (rippleCarryWire base 0) = false :=
h (.pin (rippleCarryWire base 0) false) (by simp [rippleCircuit])
simp [wireValue,hc]
| succ i ih =>
have h' : ∀ g ∈ rippleStep false base i lhs rhs, g.Holds α := by
intro g hg
exact h g (List.mem_cons.mpr (.inr (List.mem_flatMap.mpr
⟨i,List.mem_range.mpr (by omega),hg⟩)))
obtain ⟨hbit,hcarry⟩ := rippleStep_outputs false base i lhs rhs α h'
have he := add_bit_equation (α (lhs i)) (α (rhs i)) (α (rippleCarryWire base i))
rw [← hbit, ← hcarry] at he
have hp := congrArg (fun z : ℕ => z*2^i) he
simp only [Nat.add_mul,Nat.mul_assoc] at hp
have hs := ih (by omega)
simp only [wireValue_succ_bit,pow_succ]
have hh : (α (rippleCarryWire base (i+1))).toNat * (2^i*2) =
2*((α (rippleCarryWire base (i+1))).toNat * 2^i) := by ac_rfl
rw [hh]
omega
theorem rippleCircuit_subtract (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ rippleCircuit true base n lhs rhs, g.Holds α) :
∀ i ≤ n, wireValue α lhs i + (α (rippleCarryWire base i)).toNat * 2^i =
wireValue α rhs i + wireValue α (rippleBitWire base) i := by
intro i hi
induction i with
| zero =>
have hc : α (rippleCarryWire base 0) = false :=
h (.pin (rippleCarryWire base 0) false) (by simp [rippleCircuit])
simp [wireValue,hc]
| succ i ih =>
have h' : ∀ g ∈ rippleStep true base i lhs rhs, g.Holds α := by
intro g hg
exact h g (List.mem_cons.mpr (.inr (List.mem_flatMap.mpr
⟨i,List.mem_range.mpr (by omega),hg⟩)))
obtain ⟨hbit,hcarry⟩ := rippleStep_outputs true base i lhs rhs α h'
have he := subtract_bit_equation (α (lhs i)) (α (rhs i)) (α (rippleCarryWire base i))
rw [← hbit, ← hcarry] at he
have hp := congrArg (fun z : ℕ => z*2^i) he
simp only [Nat.add_mul,Nat.mul_assoc] at hp
have hs := ih (by omega)
simp only [wireValue_succ_bit,pow_succ]
have hh : (α (rippleCarryWire base (i+1))).toNat * (2^i*2) =
2*((α (rippleCarryWire base (i+1))).toNat * 2^i) := by ac_rfl
rw [hh]
omega
/-- Canonical auxiliary carry values, computed on the unchanged operands. -/
private def carryPrefix (subtract : Bool) (lhs rhs : ℕ → ℕ) (α : Assignment) : ℕ → Bool
| 0 => false
| i+1 => rippleNext subtract (α (lhs i)) (α (rhs i)) (carryPrefix subtract lhs rhs α i)
def rippleAssign (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) (k : ℕ) : Bool :=
if k < base then α k else
let i := (k-base)/8
let a := α (lhs i)
let b := α (rhs i)
let p := a ^^ b
let c := carryPrefix subtract lhs rhs α i
match (k-base)%8 with
| 0 => c
| 1 => p
| 2 => p ^^ c
| 3 => !a
| 4 => !p
| 5 => (if subtract then !a else a) && b
| 6 => (if subtract then !p else p) && c
| _ => false
theorem rippleAssign_preserves {base k : ℕ} (hk : k < base) (subtract : Bool)
(lhs rhs : ℕ → ℕ) (α : Assignment) :
rippleAssign subtract base lhs rhs α k = α k := by simp [rippleAssign,hk]
private theorem eq_aux (base i j : ℕ) (hj : j < 8) :
¬base+8*i+j < base ∧ (base+8*i+j-base)/8 = i ∧ (base+8*i+j-base)%8 = j := by
omega
private theorem rippleAssign_carry (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (rippleCarryWire base i) =
carryPrefix subtract lhs rhs α i := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 0 (by decide)
simp only [Nat.add_zero] at h hD hM
simp [rippleCarryWire,rippleAssign,h,hM]
private theorem rippleAssign_xor (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (rippleXorWire base i) = (α (lhs i) ^^ α (rhs i)) := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 1 (by decide)
simp [rippleXorWire,rippleAssign,h,hD,hM]
private theorem rippleAssign_bit (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (rippleBitWire base i) =
((α (lhs i) ^^ α (rhs i)) ^^ carryPrefix subtract lhs rhs α i) := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 2 (by decide)
simp [rippleBitWire,rippleAssign,h,hD,hM]
private theorem rippleAssign_invLeft (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (invLeftWire base i) = !α (lhs i) := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 3 (by decide)
simp [invLeftWire,rippleAssign,h,hD,hM]
private theorem rippleAssign_invXor (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (invXorWire base i) = !(α (lhs i) ^^ α (rhs i)) := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 4 (by decide)
simp [invXorWire,rippleAssign,h,hD,hM]
private theorem rippleAssign_first (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (firstCarryWire base i) =
((if subtract then !α (lhs i) else α (lhs i)) && α (rhs i)) := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 5 (by decide)
simp [firstCarryWire,rippleAssign,h,hD,hM]
private theorem rippleAssign_second (subtract : Bool) (base : ℕ) (lhs rhs : ℕ → ℕ)
(α : Assignment) (i : ℕ) :
rippleAssign subtract base lhs rhs α (secondCarryWire base i) =
((if subtract then !(α (lhs i) ^^ α (rhs i)) else (α (lhs i) ^^ α (rhs i))) &&
carryPrefix subtract lhs rhs α i) := by
obtain ⟨h,hD,hM⟩ := eq_aux base i 6 (by decide)
simp [secondCarryWire,rippleAssign,h,hD,hM]
theorem rippleCircuit_extends (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∀ g ∈ rippleCircuit subtract base n lhs rhs, g.Holds (rippleAssign subtract base lhs rhs α) := by
intro g hg
rcases List.mem_cons.mp hg with h | h
· subst g
simp [Gate.Holds,rippleAssign_carry,carryPrefix]
· obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp h
have hi' := List.mem_range.mp hi
simp only [rippleStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
cases subtract <;>
simp [Gate.Holds, rippleAssign_preserves (hL i hi'), rippleAssign_preserves (hR i hi'),
rippleAssign_carry,rippleAssign_xor,rippleAssign_bit,rippleAssign_invLeft,rippleAssign_invXor,
rippleAssign_first,rippleAssign_second,carryPrefix,rippleNext]
/-- An output with one additional high wire is exact natural addition. -/
def addOutputWire (base n : ℕ) (i : ℕ) :=
if i < n then rippleBitWire base i else rippleCarryWire base n
theorem rippleCircuit_add_exact (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ rippleCircuit false base n lhs rhs, g.Holds α) :
wireValue α (addOutputWire base n) (n+1) =
wireValue α lhs n + wireValue α rhs n := by
have hs := rippleCircuit_add base n lhs rhs α h n le_rfl
have hp : wireValue α (addOutputWire base n) n =
wireValue α (rippleBitWire base) n := by
apply wireValue_key_congr
intro i hi
simp [addOutputWire,hi]
simp [wireValue_succ_bit,hp,addOutputWire,hs]
def monusMaskWire (base n : ℕ) := base+8*n+1
def monusOutWire (base n i : ℕ) := base+8*n+2+i
def monusMask (base n : ℕ) : List Gate :=
.inv (monusMaskWire base n) (rippleCarryWire base n) ::
(List.range n).map (fun i => .conj (monusOutWire base n i) (monusMaskWire base n) (rippleBitWire base i))
def monusCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
rippleCircuit true base n lhs rhs ++ monusMask base n
theorem length_monusCircuit (base n : ℕ) (lhs rhs : ℕ → ℕ) :
(monusCircuit base n lhs rhs).length = 8*n+2 := by
simp only [monusCircuit,List.length_append,length_rippleCircuit,monusMask,List.length_cons,
List.length_map,List.length_range]
omega
theorem monusCircuit_exact (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ monusCircuit base n lhs rhs, g.Holds α) :
wireValue α (monusOutWire base n) n = wireValue α lhs n-wireValue α rhs n := by
have hRaw : ∀ g ∈ rippleCircuit true base n lhs rhs, g.Holds α :=
fun g hg => h g (List.mem_append.mpr (.inl hg))
have hSub := rippleCircuit_subtract base n lhs rhs α hRaw n le_rfl
have hBound := wireValue_lt α (rippleBitWire base) n
have hMask : α (monusMaskWire base n) = !α (rippleCarryWire base n) :=
h (.inv (monusMaskWire base n) (rippleCarryWire base n))
(by simp [monusCircuit,monusMask])
have hOut (i : ℕ) (hi : i < n) :
α (monusOutWire base n i) = (α (monusMaskWire base n) && α (rippleBitWire base i)) :=
h (.conj (monusOutWire base n i) (monusMaskWire base n) (rippleBitWire base i))
(List.mem_append.mpr (.inr (List.mem_cons.mpr (.inr (List.mem_map.mpr
⟨i,List.mem_range.mpr hi,rfl⟩)))))
cases hb : α (rippleCarryWire base n) with
| false =>
have ha : wireValue α (monusOutWire base n) n =
wireValue α (rippleBitWire base) n := by
let β : Assignment := fun i => α (rippleBitWire base i)
let γ : Assignment := fun i => α (monusOutWire base n i)
have he : wireValue γ id n = wireValue β id n := by
apply wireValue_congr
intro i hi
simp [γ,β,hOut i hi,hMask,hb]
have hval (key : ℕ → ℕ) (i : ℕ) :
wireValue (α ∘ key) id i = wireValue α key i := by
induction i with
| zero => rfl
| succ i ih => simp [wireValue,ih]
rw [show γ = α ∘ monusOutWire base n from rfl,show β = α ∘ rippleBitWire base from rfl,
hval,hval] at he
exact he
simp only [hb,Bool.toNat_false,Nat.zero_mul,Nat.add_zero] at hSub
omega
| true =>
have ha (i : ℕ) (hi : i ≤ n) : wireValue α (monusOutWire base n) i = 0 := by
induction i with
| zero => rfl
| succ i ih =>
simp [wireValue,ih (by omega),hOut i (by omega),hMask,hb]
simp only [hb,Bool.toNat_true,Nat.one_mul] at hSub
have hzero := ha n le_rfl
omega
theorem rippleCircuit_names_lt (subtract : Bool) (base n : ℕ) (lhs rhs : ℕ → ℕ)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∀ g ∈ rippleCircuit subtract base n lhs rhs, ∀ k ∈ g.names, k < base+8*n+1 := by
intro g hg k hk
rcases List.mem_cons.mp hg with rfl | hg
· simp [Gate.names,rippleCarryWire] at hk
omega
· obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp hg
have hi' := List.mem_range.mp hi
have hli := hL i hi'
have hri := hR i hi'
simp only [rippleStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
cases subtract <;>
simp [Gate.names,rippleCarryWire,rippleXorWire,rippleBitWire,invLeftWire,invXorWire,
firstCarryWire,secondCarryWire] at hk <;> omega
theorem rippleCircuit_extends_interval (subtract : Bool) (base n : ℕ)
(lhs rhs : ℕ → ℕ) (α : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∃ β : Assignment,
(∀ k, (k < base ∨ base+8*n+1 ≤ k) → β k = α k) ∧
(∀ g ∈ rippleCircuit subtract base n lhs rhs, g.Holds β) := by
let ρ := rippleAssign subtract base lhs rhs α
let β : Assignment := fun k => if k < base+8*n+1 then ρ k else α k
refine ⟨β,?_,?_⟩
· intro k hk
rcases hk with hk | hk
· simp only [β,if_pos (show k < base+8*n+1 by omega),ρ,rippleAssign_preserves hk]
· simp only [β,if_neg (Nat.not_lt_of_ge hk)]
· intro g hg
apply (g.holds_congr ρ β (fun k hk => by
simp only [β,if_pos (rippleCircuit_names_lt subtract base n lhs rhs hL hR g hg k hk)])).mp
exact rippleCircuit_extends subtract base n lhs rhs α hL hR g hg
theorem monusCircuit_extends_interval (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base) :
∃ β : Assignment,
(∀ k, (k < base ∨ base+9*n+2 ≤ k) → β k = α k) ∧
(∀ g ∈ monusCircuit base n lhs rhs, g.Holds β) := by
let ρ := rippleAssign true base lhs rhs α
let c := rippleCarryWire base n
let m := monusMaskWire base n
let mask := !ρ c
let β : Assignment := fun k =>
if k < base+9*n+2 then
if k < m then ρ k else
if k=m then mask else mask && ρ (rippleBitWire base (k-m-1))
else α k
have hm : m = base+8*n+1 := rfl
have hc : c < m := by rw [hm]; unfold c rippleCarryWire; omega
have hPrefix (k : ℕ) (hk : k < m) : β k = ρ k := by simp [β,hk,show k < base+9*n+2 by omega]
have hMask : β m = mask := by simp [β,show m < base+9*n+2 by omega]
refine ⟨β,?_,?_⟩
· intro k hk
rcases hk with hk | hk
· rw [hPrefix k (by omega)]
exact rippleAssign_preserves hk true lhs rhs α
· simp [β,Nat.not_lt_of_ge hk]
· intro g hg
rcases List.mem_append.mp hg with hg | hg
· exact (g.holds_congr ρ β (fun k hk => (hPrefix k
(rippleCircuit_names_lt true base n lhs rhs hL hR g hg k hk)).symm)).mp
(rippleCircuit_extends true base n lhs rhs α hL hR g hg)
· rcases List.mem_cons.mp hg with rfl | hg
· change β m = !β c
rw [hMask,hPrefix c hc]
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hi' := List.mem_range.mp hi
have hBit : rippleBitWire base i < m := by unfold rippleBitWire; omega
have hOut : monusOutWire base n i = m+1+i := by unfold monusOutWire; omega
change β (monusOutWire base n i) = (β m && β (rippleBitWire base i))
rw [hMask,hPrefix _ hBit,hOut]
have hNum : m+1+i-m-1 = i := by omega
simp [β,show m+1+i < base+9*n+2 by omega,show ¬m+1+i < m by omega,
show m+1+i ≠ m by omega,hNum]
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open CookLevin
private def hasHighBit (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) : Prop :=
∃ j : Fin n, i ≤ j.val ∧ α (key j.val) = true
private instance (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) :
Decidable (hasHighBit α key n i) := by unfold hasHighBit; infer_instance
private theorem hasHighBit_succ (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) (hi : i < n) :
hasHighBit α key n i ↔ α (key i) = true ∨ hasHighBit α key n (i+1) := by
constructor
· rintro ⟨j,hij,hj⟩
by_cases h : j.val=i
· exact Or.inl (by simpa [h] using hj)
· exact Or.inr ⟨j,by omega,hj⟩
· rintro (h | ⟨j,hij,hj⟩)
· exact ⟨⟨i,hi⟩,le_rfl,h⟩
· exact ⟨j,by omega,hj⟩
private theorem hasHighBit_le (α : Assignment) (key : ℕ → ℕ) (n i : ℕ)
(h : hasHighBit α key n i) : 2^i ≤ wireValue α key n := by
obtain ⟨j,hij,hj⟩ := h
have hw (u : ℕ) (hu : j.val < u) : 2^j.val ≤ wireValue α key u := by
induction u with
| zero => omega
| succ u ih =>
by_cases hU : j.val=u
· have hBit : α (key u) = true := hU ▸ hj
simp [wireValue,hU,hBit]
· have hle := ih (by have := j.isLt; omega)
rw [wireValue]
omega
exact (Nat.pow_le_pow_right (by decide) hij).trans (hw n j.isLt)
private theorem wireValue_eq_prefix (α : Assignment) (key : ℕ → ℕ) (n i : ℕ)
(hi : i ≤ n) (h : ¬hasHighBit α key n i) :
wireValue α key n = wireValue α key i := by
induction n with
| zero => exact congrArg (wireValue α key) (Nat.eq_zero_of_le_zero hi).symm
| succ n ih =>
by_cases hEq : i=n+1
· rw [hEq]
have hBit : α (key n) = false := by
by_contra hh
exact h ⟨⟨n,Nat.lt_succ_self _⟩,by change i ≤ n; omega,by simpa using hh⟩
have hn : ¬hasHighBit α key n i := by
rintro ⟨j,hj,hOn⟩
exact h ⟨j.castSucc,hj,hOn⟩
simp [wireValue,hBit,ih (by omega) hn]
private theorem highBit_iff_size (α : Assignment) (key : ℕ → ℕ) (n i : ℕ) :
hasHighBit α key n i ↔ i < (wireValue α key n).size := by
rw [← not_le, Nat.size_le]
constructor
· exact fun h => not_lt.mpr (hasHighBit_le α key n i h)
· intro h
by_contra hn
by_cases hi : i ≤ n
· exact h ((wireValue_eq_prefix α key n i hi hn) ▸ wireValue_lt α key i)
· exact h ((wireValue_lt α key n).trans_le (Nat.pow_le_pow_right (by decide) (by omega)))
def widthFlagWire (base i : ℕ) := base+i
/-- The output at index i is true exactly when the length of the binary word
is greater than i. The final sentinel flag is false. -/
def widthCircuit (base n : ℕ) (key : ℕ → ℕ) : List Gate :=
.pin (widthFlagWire base n) false ::
(List.range n).map (fun i => .disj (widthFlagWire base i) (key i) (widthFlagWire base (i+1)))
theorem length_widthCircuit (base n : ℕ) (key : ℕ → ℕ) :
(widthCircuit base n key).length = n+1 := by simp [widthCircuit]
private theorem decide_hasHighBit_succ (α : Assignment) (key : ℕ → ℕ) (n i : ℕ)
(hi : i < n) :
decide (hasHighBit α key n i) =
(α (key i) || decide (hasHighBit α key n (i+1))) := by
have he := hasHighBit_succ α key n i hi
by_cases h : hasHighBit α key n i
· rcases he.mp h with h0 | h1 <;> simp_all
· have h1 : α (key i) = false := by
cases hi : α (key i)
· rfl
· exact False.elim (h (he.mpr (.inl hi)))
have h2 : ¬ hasHighBit α key n (i+1) := fun h' => h (he.mpr (.inr h'))
simp [h,h1,h2]
theorem widthCircuit_exact (base n : ℕ) (key : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ widthCircuit base n key, g.Holds α) {i : ℕ} (hi : i ≤ n) :
α (widthFlagWire base i) = decide (i < (wireValue α key n).size) := by
have hF (k : ℕ) (hk : k ≤ n) :
α (widthFlagWire base (n-k)) = decide (hasHighBit α key n (n-k)) := by
induction k with
| zero =>
have hx : α (widthFlagWire base n) = false :=
h (.pin (widthFlagWire base n) false) (by simp [widthCircuit])
have hNo : ¬hasHighBit α key n n := by
rintro ⟨j,hj,_⟩
have := j.isLt
omega
simp [hx,hNo]
| succ k ih =>
let j := n-(k+1)
have hj : j < n := by unfold j; omega
have hp : α (widthFlagWire base j) = (α (key j) || α (widthFlagWire base (j+1))) :=
h (.disj (widthFlagWire base j) (key j) (widthFlagWire base (j+1)))
(List.mem_cons.mpr (.inr (List.mem_map.mpr ⟨j,List.mem_range.mpr hj,rfl⟩)))
have hc : j+1=n-k := by unfold j; omega
change α (widthFlagWire base j) = decide (hasHighBit α key n j)
rw [hp,hc,ih (by omega),decide_hasHighBit_succ α key n j hj,hc]
have hE := hF (n-i) (Nat.sub_le _ _)
rw [Nat.sub_sub_self hi] at hE
rw [hE]
have hiff := highBit_iff_size α key n i
by_cases h : hasHighBit α key n i
· simp [h,hiff.mp h]
· have hh : ¬i < (wireValue α key n).size := fun hn => h (hiff.mpr hn)
simp only [h,hh,decide_false]
theorem widthCircuit_extends_interval (base n : ℕ) (key : ℕ → ℕ) (α : Assignment)
(hKey : ∀ i < n, key i < base) :
∃ β : Assignment, (∀ k, k < base ∨ base+n+1 ≤ k → β k = α k) ∧
(∀ g ∈ widthCircuit base n key, g.Holds β) := by
let β : Assignment := fun k =>
if base ≤ k ∧ k ≤ base+n then decide (hasHighBit α key n (k-base)) else α k
have hFlag (i : ℕ) (hi : i ≤ n) :
β (widthFlagWire base i) = decide (hasHighBit α key n i) := by
have h : base ≤ base+i ∧ base+i ≤ base+n := by omega
simp [β,widthFlagWire,h]
have hLow (k : ℕ) (hk : k < base) : β k = α k := by simp [β,show ¬base ≤ k by omega]
refine ⟨β,?_,?_⟩
· intro k hk
rcases hk with hk | hk
· exact hLow k hk
· simp [β,show ¬k ≤ base+n by omega]
· intro g hg
rcases List.mem_cons.mp hg with rfl | hg
· change β (widthFlagWire base n) = false
have hNil : ¬hasHighBit α key n n := by
rintro ⟨j,hj,_⟩
have := j.isLt
omega
rw [hFlag n le_rfl]
simp [hNil]
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hI := List.mem_range.mp hi
change β (widthFlagWire base i) = (β (key i) || β (widthFlagWire base (i+1)))
rw [hFlag i hI.le, hFlag (i+1) hI, hLow _ (hKey i hI)]
exact decide_hasHighBit_succ α key n i hI
open scoped BigOperators in
/-- Charging one unit for each active width flag recovers the ordinary binary length. -/
theorem widthCircuit_sum (base n : ℕ) (key : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ widthCircuit base n key, g.Holds α) :
∑ i ∈ Finset.range n, (α (widthFlagWire base i)).toNat = (wireValue α key n).size := by
let k := (wireValue α key n).size
have hRange : k ≤ n := Nat.size_le.mpr (wireValue_lt α key n)
have hfilter : (Finset.range n).filter (·<k) = Finset.range k := by
ext i
simp only [Finset.mem_filter,Finset.mem_range]
omega
change ∑ i ∈ Finset.range n, (α (widthFlagWire base i)).toNat = k
calc
_ = ∑ i ∈ Finset.range n, (if i < k then 1 else 0) := by
apply Finset.sum_congr rfl
intro i hi
rw [widthCircuit_exact base n key α h (Finset.mem_range.mp hi).le]
change (decide (i < k)).toNat = _
by_cases hh : i < k <;> simp [hh]
_ = ∑ i ∈ (Finset.range n).filter (·<k), (1:ℕ) := by rw [Finset.sum_filter]
_ = k := by rw [hfilter]; simp
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open CookLevin
/-- Guard a local gate block by a literal. No auxiliary wire is needed. -/
def guarded (enable : Literal) (body : List Gate) : List Gate :=
(compile body).map fun c => Gate.assert (enable.negate :: c)
theorem length_guarded (enable : Literal) (body : List Gate) :
(guarded enable body).length ≤ 4*body.length := by
rw [guarded,List.length_map]
exact length_compile body
theorem guarded_exact (enable : Literal) (body : List Gate) (α : Assignment) :
(∀ g ∈ guarded enable body, g.Holds α) ↔
(satisfiesLiteral α enable = true → ∀ g ∈ body, g.Holds α) := by
rw [← compile_correct body α]
constructor
· intro h enabled c hc
have hg := h (Gate.assert (enable.negate::c)) (List.mem_map.mpr ⟨c,hc,rfl⟩)
change satisfiesClause α (enable.negate::c) = true at hg
rwa [satisfiesClause_cons,satisfiesLiteral_negate,enabled] at hg
· intro h g hg
obtain ⟨c,hc,rfl⟩ := List.mem_map.mp hg
change satisfiesClause α (enable.negate::c) = true
rw [satisfiesClause_cons,satisfiesLiteral_negate]
cases he : satisfiesLiteral α enable
· rfl
· simpa using h he c hc
/-- Renaming all wires commutes with literal evaluation. -/
def Literal.rename (name : ℕ → ℕ) : Literal → Literal
| .Neg r => .Neg (name r)
| .Pos r => .Pos (name r)
theorem literal_rename_correct (name : ℕ → ℕ) (α : Assignment) (value : Literal) :
satisfiesLiteral α (Literal.rename name value) = satisfiesLiteral (α ∘ name) value := by
cases value <;> rfl
def Gate.rename (name : ℕ → ℕ) : Gate → Gate
| .pin o v => .pin (name o) v
| .copy o x => .copy (name o) (name x)
| .inv o x => .inv (name o) (name x)
| .conj o x y => .conj (name o) (name x) (name y)
| .disj o x y => .disj (name o) (name x) (name y)
| .parity o x y => .parity (name o) (name x) (name y)
| .mux o s x y => .mux (name o) (name s) (name x) (name y)
| .assert c => .assert (c.map (Literal.rename name))
theorem renamedNames (name : ℕ → ℕ) (g : Gate) :
(g.rename name).names = g.names.map name := by
cases g with
| assert c =>
simp only [Gate.rename,Gate.names,List.map_map]
congr 1
funext lit
cases lit <;> rfl
| _ => rfl
theorem renamedGate_correct (name : ℕ → ℕ) (α : Assignment) (g : Gate) :
(g.rename name).Holds α ↔ g.Holds (α ∘ name) := by
cases g with
| assert c =>
have hl : satisfiesLiteral α ∘ Literal.rename name = satisfiesLiteral (α ∘ name) := by
funext l
exact literal_rename_correct name α l
simp only [Gate.rename,Gate.Holds,satisfiesClause,List.any_map,hl]
| _ => rfl
theorem renamedCircuit_correct (name : ℕ → ℕ) (α : Assignment) (body : List Gate) :
(∀ g ∈ body.map (Gate.rename name), g.Holds α) ↔ ∀ g ∈ body, g.Holds (α ∘ name) := by
simp only [List.mem_map]
constructor
· intro h g hg
exact (renamedGate_correct name α g).mp (h _ ⟨g,hg,rfl⟩)
· rintro h _ ⟨g,hg,rfl⟩
exact (renamedGate_correct name α g).mpr (h g hg)
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime
section Build
variable {α : Type} {input : α ↪ List Bool}
/-- The finite gate record consists of the corresponding named wires in unary. -/
theorem gate_of_fields {g : α → Gate} {code : α → List ℕ}
(hCode : ComputableTidilyInPolyTime code input (encList encUnary))
(he : ∀ a, (g a).code = code a) :
ComputableTidilyInPolyTime g input gateEnc :=
hCode.of_enc_eq (fun a => congrArg (encList encUnary) (he a))
theorem gate_pin (value : Bool) {out : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.pin (out a) value) input gateEnc := by
cases value <;>
first
| exact gate_of_fields (cons' (const 0) (cons' ho (const []))) (fun _ => rfl)
| exact gate_of_fields (cons' (const 1) (cons' ho (const []))) (fun _ => rfl)
theorem gate_copy {out src : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary)
(hx : ComputableTidilyInPolyTime src input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.copy (out a) (src a)) input gateEnc :=
gate_of_fields (cons' (const 2) (cons' ho (cons' hx (const [])))) (fun _ => rfl)
theorem gate_inv {out src : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary)
(hx : ComputableTidilyInPolyTime src input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.inv (out a) (src a)) input gateEnc :=
gate_of_fields (cons' (const 3) (cons' ho (cons' hx (const [])))) (fun _ => rfl)
theorem gate_conj {out x y : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary)
(hx : ComputableTidilyInPolyTime x input encUnary)
(hy : ComputableTidilyInPolyTime y input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.conj (out a) (x a) (y a)) input gateEnc :=
gate_of_fields (cons' (const 4) (cons' ho (cons' hx (cons' hy (const []))))) (fun _ => rfl)
theorem gate_disj {out x y : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary)
(hx : ComputableTidilyInPolyTime x input encUnary)
(hy : ComputableTidilyInPolyTime y input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.disj (out a) (x a) (y a)) input gateEnc :=
gate_of_fields (cons' (const 5) (cons' ho (cons' hx (cons' hy (const []))))) (fun _ => rfl)
theorem gate_parity {out x y : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary)
(hx : ComputableTidilyInPolyTime x input encUnary)
(hy : ComputableTidilyInPolyTime y input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.parity (out a) (x a) (y a)) input gateEnc :=
gate_of_fields (cons' (const 6) (cons' ho (cons' hx (cons' hy (const []))))) (fun _ => rfl)
theorem gate_mux {out s x y : α → ℕ}
(ho : ComputableTidilyInPolyTime out input encUnary)
(hs : ComputableTidilyInPolyTime s input encUnary)
(hx : ComputableTidilyInPolyTime x input encUnary)
(hy : ComputableTidilyInPolyTime y input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.mux (out a) (s a) (x a) (y a)) input gateEnc :=
gate_of_fields (cons' (const 7) (cons' ho (cons' hs (cons' hx (cons' hy (const [])))))) (fun _ => rfl)
theorem gate_assert {c : α → CookLevin.Clause}
(hc : ComputableTidilyInPolyTime (CookLevin.clauseN ∘ c) input (encList encUnary)) :
ComputableTidilyInPolyTime (fun a => Gate.assert (c a)) input gateEnc :=
gate_of_fields (cons' (const 8) hc) (fun _ => rfl)
private theorem cmp_index {base i : α → ℕ} (hb : ComputableTidilyInPolyTime base input encUnary)
(hi : ComputableTidilyInPolyTime i input encUnary) (t : ℕ) :
ComputableTidilyInPolyTime (fun a => base a+4*i a+t) input encUnary :=
unary_add.comp ((unary_add.comp (hb.prod (unary_mul.comp ((const 4).prod hi)))).prod (const t))
private theorem compareStep_poly {base i lhs rhs : α → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hi : ComputableTidilyInPolyTime i input encUnary)
(hl : ComputableTidilyInPolyTime lhs input encUnary)
(hr : ComputableTidilyInPolyTime rhs input encUnary) :
ComputableTidilyInPolyTime (fun a => compareStep (base a) (i a)
(fun _ => lhs a) (fun _ => rhs a)) input (encList gateEnc) := by
have hLt := cmp_index hb hi 0
have hEq := cmp_index hb hi 1
have hDiff := cmp_index hb hi 2
have hSame := cmp_index hb hi 3
have hSucc := unary_add.comp (hi.prod (const 1))
have hLtSucc := cmp_index hb hSucc 0
have hEqSucc := cmp_index hb hSucc 1
have result := cons' (gate_parity hDiff hl hr)
(cons' (gate_inv hSame hDiff) (cons' (gate_mux hLtSucc hDiff hr hLt)
(cons' (gate_conj hEqSucc hSame hEq) (const []))))
simpa only [compareStep,ltWire,eqWire,diffWire,sameWire,Function.comp_apply,Nat.add_zero] using result
/-- Uniformly generate the comparator given a polynomial-time address calculation
for both operand wires at a unary coordinate. -/
theorem compareCircuit_polytime {base n : α → ℕ} {lhs rhs : α → ℕ → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hn : ComputableTidilyInPolyTime n input encUnary)
(hl : ComputableTidilyInPolyTime (fun a : α × ℕ => lhs a.1 a.2)
(encPair input encUnary) encUnary)
(hr : ComputableTidilyInPolyTime (fun a : α × ℕ => rhs a.1 a.2)
(encPair input encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => compareCircuit (base a) (n a) (lhs a) (rhs a))
input (encList gateEnc) := by
have hs := compareStep_poly (hb.comp (fst input encUnary)) (snd input encUnary) hl hr
have hs' : ComputableTidilyInPolyTime
(fun a : α × ℕ => compareStep (base a.1) a.2 (lhs a.1) (rhs a.1))
(encPair input encUnary) (encList gateEnc) := hs
have hBody := flatMapWithInput (f := fun a i => compareStep (base a) i (lhs a) (rhs a))
(range.comp hn) hs'
have hLt := cmp_index hb (const 0) 0
have hEq := cmp_index hb (const 0) 1
exact cons' (gate_pin false hLt) (cons' (gate_pin true hEq) hBody)
private theorem arith_index {base i : α → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hi : ComputableTidilyInPolyTime i input encUnary) (t : ℕ) :
ComputableTidilyInPolyTime (fun a => base a+8*i a+t) input encUnary :=
unary_add.comp ((unary_add.comp (hb.prod (unary_mul.comp ((const 8).prod hi)))).prod (const t))
private theorem rippleStep_poly (subtract : Bool) {base i lhs rhs : α → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hi : ComputableTidilyInPolyTime i input encUnary)
(hl : ComputableTidilyInPolyTime lhs input encUnary)
(hr : ComputableTidilyInPolyTime rhs input encUnary) :
ComputableTidilyInPolyTime (fun a => rippleStep subtract (base a) (i a)
(fun _ => lhs a) (fun _ => rhs a)) input (encList gateEnc) := by
have hC := arith_index hb hi 0
have hP := arith_index hb hi 1
have hO := arith_index hb hi 2
have hNotA := arith_index hb hi 3
have hNotP := arith_index hb hi 4
have hS := arith_index hb hi 5
have hT := arith_index hb hi 6
have hNext := arith_index hb (unary_add.comp (hi.prod (const 1))) 0
have hFin := cons' (gate_disj hNext hS hT) (const [])
cases subtract
· have hCarr := cons' (gate_conj hS hl hr) (cons' (gate_conj hT hP hC) hFin)
exact cons' (gate_parity hP hl hr) (cons' (gate_parity hO hP hC)
(cons' (gate_inv hNotA hl) (cons' (gate_inv hNotP hP) hCarr)))
· have hCarr := cons' (gate_conj hS hNotA hr) (cons' (gate_conj hT hNotP hC) hFin)
exact cons' (gate_parity hP hl hr) (cons' (gate_parity hO hP hC)
(cons' (gate_inv hNotA hl) (cons' (gate_inv hNotP hP) hCarr)))
theorem rippleCircuit_polytime (subtract : Bool) {base n : α → ℕ} {lhs rhs : α → ℕ → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hn : ComputableTidilyInPolyTime n input encUnary)
(hl : ComputableTidilyInPolyTime (fun a : α × ℕ => lhs a.1 a.2)
(encPair input encUnary) encUnary)
(hr : ComputableTidilyInPolyTime (fun a : α × ℕ => rhs a.1 a.2)
(encPair input encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => rippleCircuit subtract (base a) (n a) (lhs a) (rhs a))
input (encList gateEnc) := by
have hs := rippleStep_poly subtract (hb.comp (fst input encUnary)) (snd input encUnary) hl hr
have hs' : ComputableTidilyInPolyTime
(fun a : α × ℕ => rippleStep subtract (base a.1) a.2 (lhs a.1) (rhs a.1))
(encPair input encUnary) (encList gateEnc) := hs
exact cons' (gate_pin false (arith_index hb (const 0) 0))
(flatMapWithInput (f := fun a i => rippleStep subtract (base a) i (lhs a) (rhs a))
(range.comp hn) hs')
theorem monusCircuit_polytime {base n : α → ℕ} {lhs rhs : α → ℕ → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hn : ComputableTidilyInPolyTime n input encUnary)
(hl : ComputableTidilyInPolyTime (fun a : α × ℕ => lhs a.1 a.2)
(encPair input encUnary) encUnary)
(hr : ComputableTidilyInPolyTime (fun a : α × ℕ => rhs a.1 a.2)
(encPair input encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => monusCircuit (base a) (n a) (lhs a) (rhs a))
input (encList gateEnc) := by
have hFirst := rippleCircuit_polytime true hb hn hl hr
have hKill := arith_index hb hn 1
have hBorrow := arith_index hb hn 0
have hOld := arith_index (hb.comp (fst input encUnary)) (snd input encUnary) 2
have hNew := unary_add.comp ((arith_index hb hn 2).comp (fst input encUnary) |>.prod (snd input encUnary))
have hGate := gate_conj hNew (hKill.comp (fst input encUnary)) hOld
have hm := mapWithInput (f := fun a i => Gate.conj (monusOutWire (base a) (n a) i)
(monusMaskWire (base a) (n a)) (rippleBitWire (base a) i)) (range.comp hn) hGate
exact listAppend' hFirst (cons' (gate_inv hKill hBorrow) hm)
theorem widthCircuit_polytime {base n : α → ℕ} {key : α → ℕ → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hn : ComputableTidilyInPolyTime n input encUnary)
(hk : ComputableTidilyInPolyTime (fun a : α × ℕ => key a.1 a.2)
(encPair input encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => widthCircuit (base a) (n a) (key a))
input (encList gateEnc) := by
have hEnd := unary_add.comp (hb.prod hn)
have ho := fst input encUnary
have hi := snd input encUnary
have hWire := unary_add.comp ((hb.comp ho).prod hi)
have hNext := unary_add.comp ((hb.comp ho).prod (unary_add.comp (hi.prod (const 1))))
have hGate := gate_disj hWire hk hNext
exact cons' (gate_pin false hEnd)
(mapWithInput (f := fun a i => Gate.disj (widthFlagWire (base a) i)
(key a i) (widthFlagWire (base a) (i+1))) (range.comp hn) hGate)
end Build
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime
private theorem filter_range_lt (m n : ℕ) (h : m ≤ n) :
(List.range n).filter (fun i => decide (i < m)) = List.range m := by
induction n with
| zero =>
have h0 : m=0 := by omega
subst m
rfl
| succ n ih =>
by_cases hr : m ≤ n
· rw [List.range_succ,List.filter_append,ih hr]
simp [show ¬ n < m by omega]
· have e : m=n+1 := by omega
subst m
apply List.filter_eq_self.mpr
intro i hi
exact decide_eq_true (List.mem_range.mp hi)
theorem unary_div_poly :
ComputableTidilyInPolyTime (fun p : ℕ × ℕ => p.1 / p.2)
(encPair encUnary encUnary) encUnary := by
let encP := encPair encUnary encUnary
have hX := fst encUnary encUnary
have hY := snd encUnary encUnary
have hP := fst encP encUnary
have hI := snd encP encUnary
have hProd := unary_mul.comp ((unary_add.comp (hI.prod (const 1))).prod (hY.comp hP))
have hPred : ComputableTidilyInPolyTime
(fun p : (ℕ × ℕ) × ℕ => decide ((p.2+1)*p.1.2 ≤ p.1.1))
(encPair encP encUnary) encBool := unary_le' hProd (hX.comp hP)
have hData := filterWithInput (test := fun p i => decide ((i+1)*p.2 ≤ p.1)) (range.comp hX) hPred
have hLen := (length encUnary).comp hData
have h := (unary_lt' (const 0) hY).ite' hLen (const 0)
convert h using 1
funext p
simp only [Function.comp_apply,decide_eq_true_eq]
by_cases hz : 0 < p.2
· rw [if_pos hz]
have hEq : (fun i => decide ((i+1)*p.2 ≤ p.1)) = (fun i => decide (i < p.1/p.2)) := by
funext i
have he : (i+1)*p.2 ≤ p.1 ↔ i < p.1/p.2 := by
rw [← Nat.le_div_iff_mul_le hz]
omega
simp [he]
rw [hEq,filter_range_lt _ _ (Nat.div_le_self _ _),List.length_range]
· have hzero : p.2 = 0 := by omega
simp [hzero]
theorem unary_mod_poly :
ComputableTidilyInPolyTime (fun p : ℕ × ℕ => p.1 % p.2)
(encPair encUnary encUnary) encUnary := by
have hX := fst encUnary encUnary
have hY := snd encUnary encUnary
have hProd := unary_mul.comp (hY.prod unary_div_poly)
have h := unary_sub.comp (hX.prod hProd)
simpa only [Function.comp_def,Nat.mod_eq_sub_mul_div] using h
theorem unary_size_poly : ComputableTidilyInPolyTime Nat.size encUnary encUnary := by
rw [show Nat.size = (fun a : ℕ => a.bits.length) from (funext Nat.size_eq_bits_len).symm]
exact length_bits_comp (natBits.comp unary_to_binary)
theorem unary_pow2_of_bound {α : Type} {input : α ↪ List Bool} {k bound : α → ℕ}
(hk : ComputableTidilyInPolyTime k input encUnary)
(hb : ComputableTidilyInPolyTime bound input encUnary)
(hle : ∀ a, 2^(k a) ≤ bound a) :
ComputableTidilyInPolyTime (fun a => 2^(k a)) input encUnary := by
have h := ComputableInPolyTime.binary_min_unary' hb.computableInPolyTime
(binary_two_pow.comp hk).computableInPolyTime
simpa [min_eq_right (hle _)] using h.tidy
theorem pow2_size_le (a : ℕ) : 2^(a.size) ≤ 2*a+1 := by
by_cases h0 : a=0
· simp [h0]
· have hp : 0 < a.size := Nat.size_pos.mpr (Nat.pos_of_ne_zero h0)
have hd : a.size-1 < a.size := by omega
have hL := Nat.lt_size.mp hd
calc
2^a.size = 2^(a.size-1)*2 := by conv_lhs => rw [show a.size=(a.size-1)+1 by omega]; rw [Nat.pow_succ]
_ ≤ 2*a+1 := by omega
theorem unary_pow2_size_poly :
ComputableTidilyInPolyTime (fun a : ℕ => 2^(a.size)) encUnary encUnary := by
have hBound := unary_add.comp
((unary_mul.comp ((const 2).prod (id' (encIn := encUnary)))).prod (const 1))
exact unary_pow2_of_bound unary_size_poly hBound pow2_size_le
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
open Turing.MultiTapeTM ComputableTidilyInPolyTime
private abbrev wordsEnc : List (List Bool) ↪ List Bool := encList encBits
/-- Read the construction dimensions from its two unary header words. -/
def inputParam (i : ℕ) (ws : List (List Bool)) : ℕ := (ws.getD i []).length
theorem inputParam_poly (i : ℕ) :
ComputableTidilyInPolyTime (inputParam i) wordsEnc encUnary := by
exact (length_bits).comp ((listGetD (encA := encBits) []).comp
((id' (encIn := wordsEnc)).prod (const i)))
@[simp] theorem inputParam_zero (prog : List Instr) (n t : ℕ) :
inputParam 0 (RobsonCNF.robsonWords (prog,n,t)) = n := by
simp [inputParam,RobsonCNF.robsonWords,unaryWord]
@[simp] theorem inputParam_one (prog : List Instr) (n t : ℕ) :
inputParam 1 (RobsonCNF.robsonWords (prog,n,t)) = t := by
simp [inputParam,RobsonCNF.robsonWords,unaryWord]
theorem layoutHeight_poly : ComputableTidilyInPolyTime layoutHeight encUnary encUnary := by
have hNat : ComputableTidilyInPolyTime (fun t : ℕ => 4*(9*t+1)-1) encUnary encUnary := by
fun_prop
exact ComputableInPolyTime.binary_size.tidy.comp (unary_to_binary.comp hNat)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open Turing.MultiTapeTM ComputableTidilyInPolyTime
private theorem twoPow_cap_poly {α : Type} {e : α ↪ List Bool} {f g : α → ℕ}
(hf : ComputableTidilyInPolyTime f e encUnary)
(hg : ComputableTidilyInPolyTime g e encUnary) :
ComputableTidilyInPolyTime (fun x => min (g x) (2^(f x))) e encUnary :=
(ComputableInPolyTime.binary_min_unary' hg.computableInPolyTime
(binary_two_pow.comp hf).computableInPolyTime).tidy
private theorem layoutHorizon_bound (t : ℕ) : layoutHorizon t ≤ 8*(9*t+1) := by
have hc : 0 < 4*(9*t+1) := by omega
change 2^(4*(9*t+1)-1).size ≤ 8*(9*t+1)
generalize hcost : 4*(9*t+1) = c at hc ⊢
have hb : 2^(c-1).size ≤ 2*c := by
cases h : (c-1).size with
| zero => simp; omega
| succ j =>
have hj : j < (c-1).size := by omega
have hlt := Nat.lt_size.mp hj
rw [pow_succ]
omega
omega
theorem layoutHorizon_poly : ComputableTidilyInPolyTime layoutHorizon encUnary encUnary := by
have hb : ComputableTidilyInPolyTime (fun t : ℕ => 8*(9*t+1)) encUnary encUnary := by fun_prop
have h := twoPow_cap_poly layoutHeight_poly hb
have he : (fun t => min (8*(9*t+1)) (2^layoutHeight t)) = layoutHorizon := by
funext t; exact min_eq_right (layoutHorizon_bound t)
rwa [he] at h
private theorem period_poly :
ComputableTidilyInPolyTime (fun p : ℕ × ℕ => 2^(min p.2 (layoutHeight p.1)))
(encPair encUnary encUnary) encUnary := by
have hp : ComputableTidilyInPolyTime (fun p : ℕ × ℕ => min p.2 (layoutHeight p.1))
(encPair encUnary encUnary) encUnary := unary_min.comp
((snd encUnary encUnary).prod (layoutHeight_poly.comp (fst encUnary encUnary)))
have hh := layoutHorizon_poly.comp (fst encUnary encUnary)
have h := twoPow_cap_poly hp hh
have he : ∀ p : ℕ × ℕ, 2^(min p.2 (layoutHeight p.1)) ≤ layoutHorizon p.1 := by
intro p
exact Nat.pow_le_pow_right (by decide) (min_le_right _ _)
simpa [min_eq_right (he _)] using h
private theorem unaryMod_poly :
ComputableTidilyInPolyTime (fun p : ℕ × ℕ => p.1 % p.2)
(encPair encUnary encUnary) encUnary := by
have ha := fst encUnary encUnary
have hb := snd encUnary encUnary
have h := ComputableInPolyTime.binary_min_unary' ha.computableInPolyTime
(binary_mod' (unary_to_binary.comp ha) (unary_to_binary.comp hb)).computableInPolyTime
simpa [min_eq_right (Nat.mod_le _ _)] using h.tidy
private def rowEnc : (ℕ × ℕ) ↪ List Bool := encPair encUnary encUnary
private def slotsAt (p : ℕ × ℕ) : List (ℕ × ℕ) :=
(((List.range (layoutHeight p.1+1)).filter fun j => p.2 % 2^j = 0).map (p.2,·))
private theorem slotsAt_poly : ComputableTidilyInPolyTime slotsAt rowEnc (encList rowEnc) := by
have ht : ComputableTidilyInPolyTime Prod.fst rowEnc encUnary := fst encUnary encUnary
have ha : ComputableTidilyInPolyTime Prod.snd rowEnc encUnary := snd encUnary encUnary
have hP := fst rowEnc encUnary
have hJ := snd rowEnc encUnary
have hR := range.comp (unary_add.comp ((layoutHeight_poly.comp ht).prod (const 1)))
have hPer := period_poly.comp ((ht.comp hP).prod hJ)
have hTest := unary_beq (unaryMod_poly.comp ((ha.comp hP).prod hPer)) (const 0)
have hF := filterWithInput
(test := fun (p : ℕ × ℕ) j => p.2 % 2^(min j (layoutHeight p.1)) == 0) hR hTest
have hOut := mapWithInput (f := fun (p : ℕ × ℕ) j => (p.2,j)) hF
((ha.comp hP).prod hJ)
convert hOut using 1
· funext p
unfold slotsAt
congr 1
apply List.filter_congr
intro j hj
have hle : j ≤ layoutHeight p.1 := Nat.lt_succ_iff.mp (List.mem_range.mp hj)
rw [min_eq_left hle]
exact Bool.eq_iff_iff.mpr (by simp only [decide_eq_true_eq,beq_iff_eq])
· rfl
theorem layoutSlots_poly : ComputableTidilyInPolyTime layoutSlots encUnary (encList rowEnc) := by
exact flatMapWithInput (range.comp layoutHorizon_poly) slotsAt_poly
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- A raw operand word taken from a physical packet input lane. Empty lanes
supply zero here and are still checked by the full row-list equality. -/
def Packet.operand (p : Packet) (i : ℕ) : ℕ :=
(p.accesses[i]?.map MemoryAccess.value).getD 0
/-- Check a packet against one fixed decoded instruction. The displayed row equalities
check all presence and write flags, addresses, input symbols, and value words. -/
def InstrPacket (op : Instr) (pc next : ℕ) (p : Packet) : Prop :=
let a := p.operand 0
let b := p.operand 1
match op with
| .loadc v =>
next = pc+1 ∧ p = ⟨none,[.write 0 v],1+bitLen v⟩
| .load j =>
next = pc+1 ∧ p = ⟨none,[.read j a,.write 0 a],1+bitLen j+bitLen a⟩
| .loadi j =>
next = pc+1 ∧ p = ⟨none,[.read j a,.read a b,.write 0 b],1+bitLen j+bitLen a+bitLen b⟩
| .store j =>
next = pc+1 ∧ p = ⟨none,[.read 0 a,.write j a],1+bitLen j+bitLen a⟩
| .storei j =>
next = pc+1 ∧ p = ⟨none,[.read j a,.read 0 b,.write a b],1+bitLen j+bitLen a+bitLen b⟩
| .add j =>
next = pc+1 ∧ p = ⟨none,[.read 0 a,.read j b,.write 0 (a+b)],1+bitLen j+bitLen a+bitLen b⟩
| .sub j =>
next = pc+1 ∧ p = ⟨none,[.read 0 a,.read j b,.write 0 (a-b)],1+bitLen j+bitLen a+bitLen b⟩
| .read =>
let v := p.input.getD 0
next = pc+1 ∧ p = ⟨some v,[.write 0 v],1+bitLen v⟩
| .jump l =>
next = l ∧ p = ⟨none,[],1+bitLen l⟩
| .jzero l =>
if a=0 then next = l ∧ p = ⟨none,[.read 0 0],1+bitLen l+bitLen 0⟩
else next = pc+1 ∧ p = ⟨none,[.read 0 a],1+bitLen l+bitLen a⟩
| .njump l r =>
(next = l ∨ next = r) ∧ p = ⟨none,[],1+bitLen l+bitLen r⟩
| .halt => False
theorem PacketStep.localInstr {prog : List Instr} {pc next : ℕ} {p : Packet}
(s : PacketStep prog pc next p) :
∃ op, prog[pc]? = some op ∧ InstrPacket op pc next p := by
cases s
all_goals refine ⟨_,‹_›,?_⟩
all_goals simp [InstrPacket,Packet.operand,MemoryAccess.read,MemoryAccess.write, *]
theorem InstrPacket.packetStep {prog : List Instr} {pc next : ℕ} {p : Packet} {op : Instr}
(hAt : prog[pc]? = some op) (h : InstrPacket op pc next p) :
PacketStep prog pc next p := by
cases op with
| loadc v =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .loadc hAt
| load j =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .load hAt
| loadi j =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .loadi hAt
| store j =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .store hAt
| storei j =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .storei hAt
| add j =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .add hAt
| sub j =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .sub hAt
| read =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .read hAt
| jump l =>
obtain ⟨hN,hP⟩ := h
rw [hN,hP]
exact .jump hAt
| jzero l =>
by_cases ha : p.operand 0 = 0
· obtain ⟨hN,hP⟩ := by simpa only [InstrPacket,ha,if_true] using h
rw [hN,hP]
exact .jzeroTaken hAt
· obtain ⟨hN,hP⟩ := by simpa only [InstrPacket,ha,if_false] using h
rw [hN,hP]
exact .jzeroNotTaken hAt ha
| njump l r =>
obtain ⟨hN,hP⟩ := h
rcases hN with hN|hN
· rw [hN,hP]
exact .njumpLeft hAt
· rw [hN,hP]
exact .njumpRight hAt
| halt => contradiction
theorem packetStep_iff_instrPacket {prog : List Instr} {pc next : ℕ} {p : Packet} {op : Instr}
(hAt : prog[pc]? = some op) :
PacketStep prog pc next p ↔ InstrPacket op pc next p := by
constructor
· intro h
obtain ⟨op',hp,hs⟩ := h.localInstr
have he := Option.some.inj (hp.symm.trans hAt)
exact he ▸ hs
· exact InstrPacket.packetStep hAt
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
abbrev PortView := Option ℕ × List MemoryAccess
/-- Missing tokens are the idle fixed slots. The extra control value `none`
denotes a halted run, and can only be followed by idle entries. -/
inductive SlotMove (prog : List Instr) :
Option PortView → Option ℕ → Option ℕ → ℕ → Prop
| idle (pc : Option ℕ) : SlotMove prog none pc pc 0
| execute {pc next : ℕ} {p : Packet} :
PacketStep prog pc next p → SlotMove prog (some p.ports) (some pc) (some next) p.cost
| halt {pc : ℕ} : prog[pc]? = some .halt →
SlotMove prog (some finalPacket.ports) (some pc) none (1+bitLen 1)
inductive SlotScan (prog : List Instr) :
List (Option PortView) → Option ℕ → Option ℕ → ℕ → Prop
| nil (pc : Option ℕ) : SlotScan prog [] pc pc 0
| cons {v : Option PortView} {vs : List (Option PortView)} {pc next last : Option ℕ} {c k : ℕ} :
SlotMove prog v pc next c → SlotScan prog vs next last k →
SlotScan prog (v::vs) pc last (c+k)
theorem SlotMove.finished {prog : List Instr} {v : Option PortView} {pc : Option ℕ} {k : ℕ}
(h : SlotMove prog v none pc k) : v = none ∧ pc = none ∧ k = 0 := by
cases h
exact ⟨rfl,rfl,rfl⟩
theorem SlotScan.finished {prog : List Instr} {vs : List (Option PortView)} {pc : Option ℕ} {k : ℕ}
(h : SlotScan prog vs none pc k) :
vs.filterMap id = [] ∧ pc = none ∧ k = 0 := by
have aux (start : Option ℕ) (h' : SlotScan prog vs start pc k) :
start = none → vs.filterMap id = [] ∧ pc = none ∧ k = 0 := by
clear h
induction h' with
| nil start => simp
| @cons v vs st next last c rem hMove hTail ih =>
intro hStart
subst st
obtain ⟨rfl,rfl,rfl⟩ := hMove.finished
simpa using ih rfl
exact aux none h rfl
theorem SlotScan.toPackets {prog : List Instr} {vs : List (Option PortView)} {pc k : ℕ}
(h : SlotScan prog vs (some pc) none k) :
∃ fin elapsed ps, PacketPath prog pc fin ps elapsed ∧ prog[fin]? = some .halt ∧
k = elapsed+(1+bitLen 1) ∧ vs.filterMap id = (ps++[finalPacket]).map Packet.ports := by
have aux (start finish : Option ℕ) (h' : SlotScan prog vs start finish k) :
∀ st, start = some st → finish = none →
∃ fin elapsed ps, PacketPath prog st fin ps elapsed ∧ prog[fin]? = some .halt ∧
k = elapsed+(1+bitLen 1) ∧ vs.filterMap id = (ps++[finalPacket]).map Packet.ports := by
clear h
induction h' with
| nil start =>
intro st h1 h2
have hbad : none = some st := h2.symm.trans h1
contradiction
| @cons v vs start next finish c k hMove hTail ih =>
intro st hStart hFinish
subst start finish
cases hMove with
| idle =>
simpa using ih st rfl rfl
| @execute _ nx p hStep =>
obtain ⟨fin,elapsed,ps,hP,hH,hk,hW⟩ := ih nx rfl rfl
exact ⟨fin,p.cost+elapsed,p::ps,.cons hStep hP,hH,by omega,
by exact congrArg (List.cons p.ports) hW⟩
| halt hH =>
obtain ⟨hv,_,hk⟩ := hTail.finished
refine ⟨st,0,[],.nil st,hH,by omega,?_⟩
change finalPacket.ports :: vs.filterMap id = [finalPacket.ports]
rw [hv]
exact aux _ _ h pc rfl rfl
theorem SlotScan.insertIdle {prog : List Instr} {vs : List (Option PortView)} {pc pc' : Option ℕ}
{k : ℕ} (h : SlotScan prog ((vs.filterMap id).map some) pc pc' k) :
SlotScan prog vs pc pc' k := by
induction vs generalizing pc pc' k with
| nil => exact h
| cons v vs ih =>
cases v with
| none =>
have hh : SlotScan prog ((vs.filterMap id).map some) pc pc' k := h
simpa only [Nat.zero_add] using
(SlotScan.cons (v:=none) (.idle pc) (ih hh))
| some a =>
change SlotScan prog (some a::(vs.filterMap id).map some) pc pc' k at h
cases h
rename_i hm ht
exact .cons hm (ih ht)
theorem PacketPath.toLiveScan {prog : List Instr} {pc fin k : ℕ} {ps : List Packet}
(h : PacketPath prog pc fin ps k) (hh : prog[fin]? = some .halt) :
SlotScan prog ((ps++[finalPacket]).map (some ∘ Packet.ports)) (some pc) none (k+(1+bitLen 1)) := by
induction h with
| nil => simpa using SlotScan.cons (.halt hh) (.nil none)
| @cons pc nx fin elapsed p ps hMove hPath ih =>
have hs := SlotScan.cons (.execute hMove) (ih hh)
simpa only [List.cons_append,List.map_cons,Function.comp_apply,Nat.add_assoc] using hs
theorem SlottedPath.tokens_live (α : Assignment) (n t : ℕ) :
let tokens := (layoutSlots t).map (fun s => if slotLive α n t s then some (slotView α n t s) else none)
tokens.filterMap id = (liveSlots α n t).map (slotView α n t) := by
unfold liveSlots
generalize layoutSlots t = xs
induction xs with
| nil => rfl
| cons s xs ih =>
dsimp only at ih
cases h : slotLive α n t s <;>
simp only [List.map_cons,List.filterMap_cons,List.filter_cons,h,Bool.false_eq_true,ite_false,ite_true,ih] <;> rfl
def slotTokens (α : Assignment) (n t : ℕ) : List (Option PortView) :=
(layoutSlots t).map fun s => if slotLive α n t s then some (slotView α n t s) else none
theorem hasSlottedPath_iff_scan (prog : List Instr) (n t : ℕ) (α : Assignment) :
HasSlottedPath prog n t α ↔
∃ k ≤ t, SlotScan prog (slotTokens α n t) (some 0) none k := by
constructor
· rintro ⟨fin,k,ps,hPath,hH,hk,hPorts⟩
refine ⟨_,hk,SlotScan.insertIdle ?_⟩
have hTok : (slotTokens α n t).filterMap id = (liveSlots α n t).map (slotView α n t) :=
SlottedPath.tokens_live α n t
rw [hTok,← hPorts,List.map_map]
exact hPath.toLiveScan hH
· rintro ⟨k,hk,hScan⟩
obtain ⟨fin,elapsed,ps,hp,hh,he,hs⟩ := hScan.toPackets
refine ⟨fin,elapsed,ps,hp,hh,by omega,?_⟩
exact hs.symm.trans (SlottedPath.tokens_live α n t)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin
structure ScanState where
control : Option ℕ
clock : ℕ
/-- One pair of neighboring control and clock words on the fixed slot array. -/
def SlotAdvance (prog : List Instr) (v : Option PortView) (u w : ScanState) : Prop :=
∃ c, SlotMove prog v u.control w.control c ∧ w.clock = u.clock+c
def ScanState.inControlRange (prog : List Instr) (s : ScanState) : Prop :=
∀ j, s.control = some j → j < prog.length
theorem SlotMove.controlRange {prog : List Instr} {v : Option PortView} {pc next : Option ℕ}
{c : ℕ} (h : SlotMove prog v pc next c)
(hNext : ∀ j, next = some j → j < prog.length) :
∀ j, pc = some j → j < prog.length := by
cases h with
| idle => exact hNext
| execute hStep =>
obtain ⟨op,hi,_⟩ := hStep.localInstr
intro j hj
obtain rfl := Option.some.inj hj
exact (List.getElem?_eq_some_iff.mp hi).choose
| halt hH =>
intro j hj
obtain rfl := Option.some.inj hj
exact (List.getElem?_eq_some_iff.mp hH).choose
theorem SlotScan.toIndexed {prog : List Instr} {tokens : List (Option PortView)}
{pc finish : Option ℕ} {k : ℕ}
(h : SlotScan prog tokens pc finish k) (m t : ℕ) (hb : m+k ≤ t)
(hFin : ∀ j, finish = some j → j < prog.length) :
∃ states : Fin (tokens.length+1) → ScanState,
states 0 = ⟨pc,m⟩ ∧ states (Fin.last tokens.length) = ⟨finish,m+k⟩ ∧
(∀ i, (states i).clock ≤ t ∧ (states i).inControlRange prog) ∧
∀ i : Fin tokens.length, SlotAdvance prog tokens[i] (states i.castSucc) (states i.succ) := by
induction h generalizing m with
| nil pc =>
refine ⟨fun _ => ⟨pc,m⟩,rfl,?_,fun _ => ⟨by omega,hFin⟩,fun i => Fin.elim0 i⟩
simp
| @cons v vs pc next finish c k hv hs ih =>
obtain ⟨states,hFirst,hLast,hBound,hMove⟩ := ih (m+c) (by omega) hFin
let ss : Fin ((v::vs).length+1) → ScanState := Fin.cons ⟨pc,m⟩ states
have hF : ss 0 = ⟨pc,m⟩ := Fin.cons_zero ..
have hSucc (i : Fin (vs.length+1)) : ss i.succ = states i := Fin.cons_succ ..
refine ⟨ss,hF,?_,?_,?_⟩
· rw [show Fin.last (v::vs).length = (Fin.last vs.length).succ from rfl,hSucc,hLast]
simp only [Nat.add_assoc]
· intro i
refine Fin.cases ?_ (fun j => ?_) i
· rw [hF]
have hm : m ≤ t := by omega
refine ⟨hm, hv.controlRange ?_⟩
have hn := (hBound 0).2
rw [hFirst] at hn
exact hn
· rw [hSucc]
exact hBound j
· intro i
refine Fin.cases ?_ (fun j => ?_) i
· change SlotAdvance prog v (ss 0) (ss (Fin.succ (0 : Fin (vs.length+1))))
rw [hF,hSucc,hFirst]
exact ⟨c,hv,rfl⟩
· change SlotAdvance prog vs[j] (ss (Fin.succ j.castSucc)) (ss (Fin.succ j.succ))
rw [hSucc,hSucc]
exact hMove j
theorem SlotScan.ofIndexed {prog : List Instr} (tokens : List (Option PortView))
(states : Fin (tokens.length+1) → ScanState)
(h : ∀ i : Fin tokens.length, SlotAdvance prog tokens[i] (states i.castSucc) (states i.succ)) :
∃ k, SlotScan prog tokens (states 0).control (states (Fin.last tokens.length)).control k ∧
(states (Fin.last tokens.length)).clock = (states 0).clock+k := by
induction tokens with
| nil =>
refine ⟨0,?_,by rfl⟩
exact .nil _
| cons v vs ih =>
let tail : Fin (vs.length+1) → ScanState := Fin.tail states
have hTail (i : Fin vs.length) : SlotAdvance prog vs[i] (tail i.castSucc) (tail i.succ) :=
h i.succ
obtain ⟨k,hs,hclock⟩ := ih tail hTail
obtain ⟨c,hv,he⟩ := h 0
refine ⟨c+k, .cons hv hs,?_⟩
change (states (Fin.last (v::vs).length)).clock = (states (Fin.succ (0 : Fin (vs.length+1)))).clock+k at hclock
change (states (Fin.succ (0 : Fin (vs.length+1)))).clock = (states 0).clock+c at he
omega
/-- The whole control/clock checker is a fixed adjacent-state relation. Every accepting
control word ranges over the program indices plus the unique halted sentinel. -/
theorem hasSlottedPath_iff_indexed (prog : List Instr) (n t : ℕ) (α : Assignment) :
HasSlottedPath prog n t α ↔
let tokens := slotTokens α n t
∃ states : Fin (tokens.length+1) → ScanState,
states 0 = ⟨some 0,0⟩ ∧ (states (Fin.last tokens.length)).control = none ∧
(∀ i, (states i).clock ≤ t ∧ (states i).inControlRange prog) ∧
∀ i : Fin tokens.length, SlotAdvance prog tokens[i] (states i.castSucc) (states i.succ) := by
rw [hasSlottedPath_iff_scan]
dsimp only
constructor
· rintro ⟨k,hk,hs⟩
obtain ⟨states,hStart,hEnd,hBounds,hSteps⟩ := hs.toIndexed 0 t (by omega)
(fun _ h => by contradiction)
exact ⟨states,hStart,congrArg ScanState.control hEnd,hBounds,hSteps⟩
· rintro ⟨states,hStart,hEnd,hBounds,hSteps⟩
obtain ⟨k,hs,hClock⟩ := SlotScan.ofIndexed _ _ hSteps
refine ⟨k,?_,?_⟩
· have hTop := (hBounds (Fin.last _)).1
rw [hStart] at hClock
change (states (Fin.last (slotTokens α n t).length)).clock = 0+k at hClock
omega
· rw [hStart,hEnd] at hs
exact hs
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
/-- The transition at one scheduled slot can be checked directly on its raw
ports and neighboring state words, without quantifying over machine packets. -/
def LocalAdvance (prog : List Instr) (v : Option PortView) (u w : ScanState) : Prop :=
match v,u.control,w.control with
| none,_,_ => u = w
| some x,some pc,some next =>
u.clock ≤ w.clock ∧ ∃ op, prog[pc]? = some op ∧
InstrPacket op pc next ⟨x.1,x.2,w.clock-u.clock⟩
| some x,some pc,none =>
prog[pc]? = some .halt ∧ x = finalPacket.ports ∧ w.clock = u.clock+(1+bitLen 1)
| some _,none,_ => False
theorem slotAdvance_iff_localAdvance (prog : List Instr) (v : Option PortView) (u w : ScanState) :
SlotAdvance prog v u w ↔ LocalAdvance prog v u w := by
rcases u with ⟨pc,m⟩
rcases w with ⟨next,k⟩
constructor
· rintro ⟨c,h,hClock⟩
change k = m+c at hClock
subst k
cases h with
| idle => rfl
| @execute pc next p hStep =>
have hPacket : (⟨p.ports.1,p.ports.2,m+p.cost-m⟩ : Packet) = p := by
simp only [Nat.add_sub_cancel_left]
cases p
rfl
change m ≤ m+p.cost ∧ ∃ op, prog[pc]? = some op ∧ InstrPacket op pc next
⟨p.ports.1,p.ports.2,m+p.cost-m⟩
rw [hPacket]
exact ⟨Nat.le_add_right _ _,hStep.localInstr⟩
| halt hh => exact ⟨hh,rfl,rfl⟩
· intro h
cases v with
| none =>
have he : (⟨pc,m⟩ : ScanState) = ⟨next,k⟩ := h
cases he
exact ⟨0,.idle pc,rfl⟩
| some x =>
cases pc with
| none => contradiction
| some pc =>
cases next with
| none =>
obtain ⟨hh,hv,hc⟩ := h
subst x
exact ⟨_,.halt hh,hc⟩
| some next =>
obtain ⟨hmon,op,hOp,hRule⟩ := h
have hStep : PacketStep prog pc next ⟨x.1,x.2,k-m⟩ := hRule.packetStep hOp
exact ⟨k-m,.execute hStep,by exact (Nat.add_sub_of_le (show m ≤ k from hmon)).symm⟩
end CNFEncComplexity.Robson
namespace CNFEncComplexity.RobsonCNF
open CookLevin
def widthChainCount (h j : ℕ) : ℕ := 2^(h-j)
def widthChainSample (j k : ℕ) : ℕ := (k+1)*2^j-1
def widthChainWire (base h j k : ℕ) : ℕ := base+j*(2^h+1)+k
def widthChain (base h j : ℕ) (flags : ℕ → ℕ) : List Gate :=
.pin (widthChainWire base h j 0) false ::
(List.range (widthChainCount h j)).map (fun k => .parity
(widthChainWire base h j (k+1)) (widthChainWire base h j k) (flags (widthChainSample j k)))
/-- Convert unary high-bit flags into the binary bit length by parity of every
second, fourth, and subsequent power-of-two spaced flag. -/
def binaryWidthCircuit (base h : ℕ) (flags : ℕ → ℕ) : List Gate :=
(List.range (h+1)).flatMap fun j => widthChain base h j flags
def binaryWidthWire (base h j : ℕ) : ℕ :=
widthChainWire base h j (widthChainCount h j)
theorem widthChain_sample_iff {j k len : ℕ} :
widthChainSample j k < len ↔ k < len / 2^j := by
have hp : 0 < (k+1)*2^j := Nat.mul_pos (by omega) (Nat.two_pow_pos _)
unfold widthChainSample
calc
_ ↔ (k+1)*2^j ≤ len := by omega
_ ↔ k+1 ≤ len/2^j := (Nat.le_div_iff_mul_le (Nat.two_pow_pos _)).symm
_ ↔ _ := Nat.succ_le_iff
private theorem widthChain_decide_eq (j k len : ℕ) :
decide (widthChainSample j k < len) = decide (k < len / 2^j) := by
by_cases h : widthChainSample j k < len
· simp [h,widthChain_sample_iff.mp h]
· have hh : ¬ k < len / 2^j := fun h' => h (widthChain_sample_iff.mpr h')
simp [h,hh]
private theorem widthChain_sample_lt {h j k : ℕ} (hj : j ≤ h) (hk : k < widthChainCount h j) :
widthChainSample j k < 2^h := by
have hDiv : (2:ℕ)^h / 2^j = widthChainCount h j := by
rw [show (2:ℕ)^h = 2^(h-j)*2^j from (Nat.pow_sub_mul_pow 2 hj).symm,
Nat.mul_div_cancel _ (Nat.two_pow_pos _)]
rfl
exact widthChain_sample_iff.mpr (hDiv.symm ▸ hk)
private theorem widthChain_parity (k q : ℕ) :
Bool.xor ((min k q).testBit 0) (decide (k < q)) = (min (k+1) q).testBit 0 := by
by_cases h : k < q
· rw [min_eq_left h.le,min_eq_left (by omega),show decide (k < q) = true from by simp [h],
Nat.testBit_zero,Nat.testBit_zero]
simp only [Bool.xor_true]
have hh : (k+1)%2=1 ↔ ¬k%2=1 := by omega
by_cases ho : k%2=1
· simp [ho,show ¬(k+1)%2=1 from fun hx => hh.mp hx ho]
· simp [ho,hh.mpr ho]
· rw [min_eq_right (by omega),min_eq_right (by omega),show decide (k < q) = false from by simp [h]]
cases (q.testBit 0) <;> rfl
theorem binaryWidthCircuit_exact (base h : ℕ) (flags : ℕ → ℕ) (α : Assignment)
{len : ℕ} (hl : len ≤ 2^h)
(hf : ∀ i < 2^h, α (flags i) = decide (i < len))
(hc : ∀ g ∈ binaryWidthCircuit base h flags, g.Holds α)
{j : ℕ} (hj : j ≤ h) :
α (binaryWidthWire base h j) = len.testBit j := by
have hChain : ∀ g ∈ widthChain base h j flags, g.Holds α := by
intro g hg
apply hc
exact List.mem_flatMap.mpr ⟨j,List.mem_range.mpr (by omega),hg⟩
let count := widthChainCount h j
let q := len / 2^j
have hValue (k : ℕ) (hk : k ≤ count) :
α (widthChainWire base h j k) = (min k q).testBit 0 := by
induction k with
| zero =>
have hp := hChain (.pin (widthChainWire base h j 0) false) (by simp [widthChain])
change α (widthChainWire base h j 0) = false at hp
simpa only [Nat.zero_min,Nat.testBit_zero,Nat.zero_mod,zero_ne_one,decide_false] using hp
| succ k ih =>
have hk' : k < widthChainCount h j := by exact hk
have hp := hChain (.parity (widthChainWire base h j (k+1))
(widthChainWire base h j k) (flags (widthChainSample j k)))
(List.mem_cons.mpr (.inr (List.mem_map.mpr ⟨k,List.mem_range.mpr hk',rfl⟩)))
change α (widthChainWire base h j (k+1)) =
Bool.xor (α (widthChainWire base h j k)) (α (flags (widthChainSample j k))) at hp
rw [hp,ih hk'.le,hf _ (widthChain_sample_lt hj hk')]
have hs : decide (widthChainSample j k < len) = decide (k < q) :=
widthChain_decide_eq _ _ _
rw [hs,widthChain_parity]
have hQ : q ≤ count := by
have hProd : count*2^j = 2^h := Nat.pow_sub_mul_pow 2 hj
have hlt : len < (count+1)*2^j := by
rw [Nat.add_mul,Nat.one_mul,hProd]
have hp := Nat.two_pow_pos j
omega
exact Nat.le_of_lt_succ ((Nat.div_lt_iff_lt_mul (Nat.two_pow_pos _)).2 hlt)
unfold binaryWidthWire
rw [hValue count le_rfl,min_eq_right hQ,Nat.testBit_zero,Nat.testBit_eq_decide_div_mod_eq]
private theorem widthChain_count_sum (h : ℕ) :
((List.range (h+1)).map (widthChainCount h)).sum + 1 = 2*2^h := by
induction h with
| zero => rfl
| succ h ih =>
rw [List.range_succ_eq_map,List.map_cons,List.map_map,List.sum_cons]
have hf : widthChainCount (h+1) ∘ Nat.succ = widthChainCount h := by
funext j
simp [widthChainCount,Function.comp_apply]
rw [hf]
have hp : widthChainCount (h+1) 0 = 2^h*2 := by simp [widthChainCount,pow_succ]
rw [hp,pow_succ]
omega
theorem length_binaryWidthCircuit (base h : ℕ) (flags : ℕ → ℕ) :
(binaryWidthCircuit base h flags).length ≤ 3*2^h := by
have hlen (js : List ℕ) : (js.flatMap (fun j => widthChain base h j flags)).length =
js.length+(js.map (widthChainCount h)).sum := by
induction js with
| nil => rfl
| cons j js ih => simp [widthChain]; omega
unfold binaryWidthCircuit
rw [hlen,List.length_range]
have hs := widthChain_count_sum h
have hh (x : ℕ) : x+1 ≤ (2:ℕ)^x := by
induction x with
| zero => decide
| succ x ih => rw [pow_succ]; omega
have hBound := hh h
omega
/-- Set the running parities from the prescribed domain length, preserving all
wires outside the rectangular scratch region. -/
theorem binaryWidthCircuit_extends (base h : ℕ) (flags : ℕ → ℕ) (α : Assignment)
{len : ℕ} (hf : ∀ i < 2^h, flags i < base ∧ α (flags i) = decide (i < len)) :
∃ β : Assignment,
(∀ r, r < base ∨ base+(h+1)*(2^h+1) ≤ r → β r = α r) ∧
∀ g ∈ binaryWidthCircuit base h flags, g.Holds β := by
let stride := 2^h+1
let β : Assignment := fun r =>
if base ≤ r ∧ r < base+(h+1)*stride then
(min ((r-base)%stride) (len / 2^((r-base)/stride))).testBit 0
else α r
have hBlock {j k : ℕ} (hj : j ≤ h) (hk : k < stride) :
β (widthChainWire base h j k) = (min k (len/2^j)).testBit 0 := by
have hLo : j*stride ≤ j*stride+k := Nat.le_add_right _ _
have hHi : j*stride+k < (j+1)*stride := by rw [Nat.add_mul,Nat.one_mul]; omega
have hBound := hHi.trans_le (Nat.mul_le_mul_right stride (show j+1 ≤ h+1 from by omega))
have he : base ≤ base+j*stride+k ∧ base+j*stride+k < base+(h+1)*stride := by omega
have hSub : base+j*stride+k-base = j*stride+k := by omega
have hDiv : (j*stride+k)/stride=j := Nat.div_eq_of_lt_le hLo hHi
have hMod : (j*stride+k)%stride=k := by
rw [Nat.add_mod,Nat.mul_mod_left,Nat.zero_add,Nat.mod_mod,Nat.mod_eq_of_lt hk]
unfold β widthChainWire
change (if base ≤ base+j*stride+k ∧ base+j*stride+k < base+(h+1)*stride then _ else _) = _
rw [if_pos he,hSub,hDiv,hMod]
have hKeep (r : ℕ) (hr : r < base ∨ base+(h+1)*stride ≤ r) : β r = α r := by
unfold β
exact if_neg (by omega)
refine ⟨β,hKeep,?_⟩
intro g hg
obtain ⟨j,hj,hg⟩ := List.mem_flatMap.mp hg
have jLe : j ≤ h := Nat.le_of_lt_succ (List.mem_range.mp hj)
have hCount : widthChainCount h j ≤ 2^h := Nat.pow_le_pow_right (by decide) (Nat.sub_le _ _)
have hPos : 0 < stride := Nat.succ_pos _
rcases List.mem_cons.mp hg with rfl | hg
· change β (widthChainWire base h j 0) = false
rw [hBlock jLe hPos]
simp
· obtain ⟨k,hk,rfl⟩ := List.mem_map.mp hg
have hk' := List.mem_range.mp hk
have hk₁ : k+1 < stride := by unfold stride; omega
have hF := hf _ (widthChain_sample_lt jLe hk')
change β (widthChainWire base h j (k+1)) =
Bool.xor (β (widthChainWire base h j k)) (β (flags (widthChainSample j k)))
rw [hBlock jLe hk₁,hBlock jLe (by omega),hKeep _ (.inl hF.1),hF.2]
rw [widthChain_decide_eq,widthChain_parity]
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open Turing.MultiTapeTM Turing.MultiTapeTM.ComputableTidilyInPolyTime
private theorem binaryWidthWire_poly {δ : Type} {input : δ ↪ List Bool}
{base h j k : δ → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hw : ComputableTidilyInPolyTime (fun a => 2^(h a)) input encUnary)
(hj : ComputableTidilyInPolyTime j input encUnary)
(hk : ComputableTidilyInPolyTime k input encUnary) :
ComputableTidilyInPolyTime (fun a => widthChainWire (base a) (h a) (j a) (k a)) input encUnary :=
unary_add.comp ((unary_add.comp (hb.prod
(unary_mul.comp (hj.prod (unary_add.comp (hw.prod (const 1))))))).prod hk)
/-- Uniformly list the parity gates given a unary bound for the dyadic word width. -/
theorem binaryWidthCircuit_polytime {δ : Type} {input : δ ↪ List Bool}
{base h : δ → ℕ} {flags : δ → ℕ → ℕ}
(hb : ComputableTidilyInPolyTime base input encUnary)
(hh : ComputableTidilyInPolyTime h input encUnary)
(hw : ComputableTidilyInPolyTime (fun a => 2^(h a)) input encUnary)
(hFlags : ComputableTidilyInPolyTime (fun p : δ × ℕ => flags p.1 p.2)
(encPair input encUnary) encUnary) :
ComputableTidilyInPolyTime (fun a => binaryWidthCircuit (base a) (h a) (flags a))
input (encList gateEnc) := by
let encJ := encPair input encUnary
have hX := fst input encUnary
have hJ := snd input encUnary
have hH := hh.comp hX
have hW := hw.comp hX
have hBase := hb.comp hX
have hDiff := unary_sub.comp (hH.prod hJ)
have hCount : ComputableTidilyInPolyTime (fun p : δ × ℕ => widthChainCount (h p.1) p.2)
encJ encUnary :=
unary_pow2_of_bound hDiff hW (fun _ => Nat.pow_le_pow_right (by decide) (Nat.sub_le _ _))
have hMin : ComputableTidilyInPolyTime (fun p : δ × ℕ => min p.2 (h p.1)) encJ encUnary := by
have hMin := (unary_le' hJ hH).ite' hJ hH
refine hMin.of_enc_eq ?_
intro p
simp [Function.comp_apply,min_def]
have hPow : ComputableTidilyInPolyTime (fun p : δ × ℕ => 2^(min p.2 (h p.1))) encJ encUnary :=
unary_pow2_of_bound hMin hW (fun _ => Nat.pow_le_pow_right (by decide) (min_le_right _ _))
have hY := fst encJ encUnary
have hK := snd encJ encUnary
have hKNext := unary_add.comp (hK.prod (const 1))
have hDist := hPow.comp hY
have hIdx := unary_sub.comp ((unary_mul.comp (hKNext.prod hDist)).prod (const 1))
have hInp := hFlags.comp ((hX.comp hY).prod hIdx)
have hWStart := binaryWidthWire_poly hBase hW hJ (const 0)
have hAux := binaryWidthWire_poly (hBase.comp hY) (hW.comp hY) (hJ.comp hY) hK
have hAuxNext := binaryWidthWire_poly (hBase.comp hY) (hW.comp hY) (hJ.comp hY) hKNext
let step (p : δ × ℕ) (k : ℕ) := Gate.parity
(widthChainWire (base p.1) (h p.1) p.2 (k+1)) (widthChainWire (base p.1) (h p.1) p.2 k)
(flags p.1 (widthChainSample (min p.2 (h p.1)) k))
have hStep : ComputableTidilyInPolyTime (fun p : (δ × ℕ) × ℕ => step p.1 p.2)
(encPair encJ encUnary) gateEnc := gate_parity hAuxNext hAux hInp
let chain (a : δ) (j : ℕ) := .pin (widthChainWire (base a) (h a) j 0) false ::
(List.range (widthChainCount (h a) j)).map (step (a,j))
have hChain : ComputableTidilyInPolyTime (fun p : δ × ℕ => chain p.1 p.2) encJ (encList gateEnc) :=
cons' (gate_pin false hWStart) (mapWithInput (range.comp hCount) hStep)
have hRange := range.comp (unary_add.comp (hh.prod (const 1)))
have hAll := flatMapWithInput (f := chain) hRange hChain
refine hAll.of_enc_eq ?_
intro a
apply congrArg (encList gateEnc)
unfold binaryWidthCircuit
apply List.flatMap_congr
intro j hj
have hj' : j ≤ h a := Nat.le_of_lt_succ (List.mem_range.mp hj)
unfold chain widthChain
congr 1
unfold step
simp [min_eq_left hj']
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
open CookLevin
def ancestorAt (s : ℕ × ℕ) (j : ℕ) : ℕ × ℕ := (s.1 / 2^j * 2^j,j)
theorem ancestorAt_mem {t : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t)
{j : ℕ} (hj : j ≤ layoutHeight t) : ancestorAt s j ∈ layoutSlots t := by
rw [layout_mem]
exact ⟨(Nat.div_mul_le_self ..).trans_lt (layout_mem.mp hs).1,hj,Nat.mul_mod_left ..⟩
private theorem aligned_floor_eq {a b j : ℕ} (hb : b % 2^j = 0) :
a / 2^j * 2^j = b ↔ b ≤ a ∧ a < b + 2^j := by
have hB := Nat.mod_add_div b (2^j)
rw [hb,Nat.zero_add,Nat.mul_comm] at hB
constructor
· intro he
have hA := Nat.mod_add_div a (2^j)
rw [Nat.mul_comm,he] at hA
have hMod := Nat.mod_lt a (Nat.two_pow_pos j)
omega
· rintro ⟨h₁,h₂⟩
have hDiv : a / 2^j = b / 2^j := by
apply Nat.div_eq_of_lt_le
· rwa [hB]
· rwa [Nat.add_mul,Nat.one_mul,hB]
rwa [hDiv]
private theorem aligned_separation {a b j k : ℕ} (ha : a % 2^j = 0) (hb : b % 2^k = 0)
(hj : j ≤ k) (hab : a < b) : a+2^j ≤ b := by
have hB : b % 2^j = 0 :=
Nat.dvd_iff_mod_eq_zero.mp ((Nat.pow_dvd_pow 2 hj).trans (Nat.dvd_iff_mod_eq_zero.mpr hb))
have heA := Nat.mod_add_div a (2^j)
have heB := Nat.mod_add_div b (2^j)
rw [ha,Nat.zero_add] at heA
rw [hB,Nat.zero_add] at heB
have hIndex : a/2^j < b/2^j := Nat.lt_of_mul_lt_mul_left (by rwa [heA,heB])
have hh := Nat.mul_le_mul_left (2^j) hIndex
rwa [Nat.succ_eq_add_one,Nat.mul_add,Nat.mul_one,heA,heB] at hh
private theorem nested_aligned {t : ℕ} {s r : ℕ × ℕ}
(hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (he : s ≠ r) (hle : s.2 ≤ r.2)
(ho : ¬(s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1)) :
s.2 < r.2 ∧ r = ancestorAt s r.2 := by
rcases s with ⟨a,j⟩
rcases r with ⟨b,k⟩
have hA := (layout_mem.mp hs).2.2
have hB := (layout_mem.mp hr).2.2
dsimp at ho hle ⊢
have hBA : b ≤ a := by
by_contra! h
exact ho (.inl (aligned_separation hA hB hle h))
have hJK : j < k := by
by_contra! hjk
have hEq : j=k := by omega
subst k
have hab : a=b := by
by_contra! he
have hAB : b < a := by omega
exact ho (.inr (aligned_separation hB hA le_rfl hAB))
exact he (by simp [hab])
have hAB : a < b+2^k := by omega
refine ⟨hJK,?_⟩
exact congrArg (fun a => (a,k)) ((aligned_floor_eq hB).mpr ⟨hBA,hAB⟩).symm
theorem overlap_iff_ancestor {t : ℕ} {s r : ℕ × ℕ}
(hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (hn : s ≠ r) :
¬(s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1) ↔
(s.2 < r.2 ∧ r = ancestorAt s r.2) ∨ (r.2 < s.2 ∧ s = ancestorAt r s.2) := by
constructor
· intro ho
rcases le_total s.2 r.2 with h | h
· exact .inl (nested_aligned hs hr hn h ho)
· exact .inr (nested_aligned hr hs (Ne.symm hn) h (fun h' => ho h'.symm))
· have aux {s r : ℕ × ℕ} (hr : r ∈ layoutSlots t) (he : r = ancestorAt s r.2) :
¬(s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1) := by
have hEq := (congrArg Prod.fst he).symm
have hBounds := (aligned_floor_eq (layout_mem.mp hr).2.2).mp hEq
have hP : 0 < 2^s.2 := Nat.two_pow_pos _
omega
rintro (⟨_,ho⟩|⟨_,ho⟩)
· exact aux hr ho
· exact fun hh => aux hs ho hh.symm
private theorem pairwise_either {δ : Type} {R : δ → δ → Prop} {xs : List δ}
(h : xs.Pairwise R) {a b : δ} (ha : a ∈ xs) (hb : b ∈ xs) (hne : a ≠ b) :
R a b ∨ R b a := by
induction xs with
| nil => contradiction
| cons x xs ih =>
obtain ⟨hrel,htail⟩ := List.pairwise_cons.mp h
rcases List.mem_cons.mp ha with hA|hA <;> rcases List.mem_cons.mp hb with hB|hB
· exact False.elim (hne (hA.trans hB.symm))
· exact .inl (hA.symm ▸ hrel b hB)
· exact .inr (hB.symm ▸ hrel a hA)
· exact ih htail hA hB
private def slotOrderKey (t : ℕ) (s : ℕ × ℕ) : ℕ := s.1*(layoutHeight t+1)+s.2
/-- In the existing start-time slot order, disjointness is equivalent to saying
that no both-active pair consists of a slot and a strict aligned ancestor. -/
theorem liveSlots_disjoint_iff (α : Assignment) (n t : ℕ) :
(liveSlots α n t).Pairwise (fun s r => s.1+2^s.2 ≤ r.1) ↔
∀ s ∈ layoutSlots t, ∀ j, s.2 < j → j ≤ layoutHeight t →
¬(slotLive α n t s = true ∧ slotLive α n t (ancestorAt s j) = true) := by
have hOrd : (layoutSlots t).Pairwise (fun s r => slotOrderKey t s < slotOrderKey t r) :=
layout_sorted t
have hOrdLive := hOrd.filter (slotLive α n t)
have hIn (s : ℕ × ℕ) : s ∈ liveSlots α n t ↔ s ∈ layoutSlots t ∧ slotLive α n t s = true :=
List.mem_filter
constructor
· intro hp s hs j hj hJ hl
let r := ancestorAt s j
have hr : r ∈ layoutSlots t := ancestorAt_mem hs hJ
have hn : s ≠ r := by
intro he
have hSnd : s.2=j := congrArg Prod.snd he
omega
have h₁ := (hIn _).mpr ⟨hs,hl.1⟩
have h₂ := (hIn _).mpr ⟨hr,hl.2⟩
have hOv := (overlap_iff_ancestor hs hr hn).mpr (.inl ⟨hj,rfl⟩)
exact hOv (pairwise_either hp h₁ h₂ hn)
· intro h
apply hOrdLive.imp_of_mem
intro s r hs hr ho
obtain ⟨hs,ha⟩ := (hIn _).mp hs
obtain ⟨hr,hb⟩ := (hIn _).mp hr
have hNot : s ≠ r := fun he => (Nat.ne_of_lt ho) (congrArg _ he)
have hl : s.1 ≤ r.1 := by
by_contra! hc
have hd : (r.1+1)*(layoutHeight t+1) ≤ s.1*(layoutHeight t+1) :=
Nat.mul_le_mul_right (layoutHeight t+1) hc
rw [Nat.add_mul,Nat.one_mul] at hd
have hLvl := (layout_mem.mp hr).2.1
unfold slotOrderKey at ho
omega
have hDisj : s.1+2^s.2 ≤ r.1 ∨ r.1+2^r.2 ≤ s.1 := by
by_contra hOverlap
rcases (overlap_iff_ancestor hs hr hNot).mp hOverlap with ⟨hJ,he⟩|⟨hJ,he⟩
· exact h _ hs _ hJ (layout_mem.mp hr).2.1 ⟨ha,he ▸ hb⟩
· exact h _ hr _ hJ (layout_mem.mp hs).2.1 ⟨hb,he ▸ ha⟩
rcases hDisj with hA|hB
· exact hA
· have hP : 0 < 2^r.2 := Nat.two_pow_pos _
omega
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def slotGuardGates (n t : ℕ) (s : ℕ × ℕ) : List Gate :=
([0,3,8,13].map fun f => .assert [.Pos (port n t s 18 0),.Neg (port n t s f 0)]) ++
(((List.range (layoutHeight t+1)).filter fun j => s.2 < j).map fun j =>
.assert [.Neg (port n t s 18 0),.Neg (port n t (ancestorAt s j) 18 0)])
def slotShapeGates (n t : ℕ) : List Gate :=
(layoutSlots t).flatMap (slotGuardGates n t)
theorem no_portInput_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
portInput α n t s = none ↔ α (port n t s 0 0) = false := by
cases he : α (port n t s 0 0) <;> simp [portInput,he]
theorem no_portMemory_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) :
portMemory α n t s i = none ↔ α (port n t s (3+5*i) 0) = false := by
cases he : α (port n t s (3+5*i) 0) <;> simp [portMemory,he]
theorem no_slotRows_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
slotRows α n t s = [] ↔ ∀ i < 3, α (port n t s (3+5*i) 0) = false := by
simp [slotRows,List.filterMap_eq_nil_iff,no_portMemory_iff]
private theorem assert_pn (α : Assignment) (p q : ℕ) :
(Gate.assert [.Pos p,.Neg q]).Holds α ↔ (α p = false → α q = false) := by
cases hp : α p <;> cases hq : α q <;> simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hp,hq]
private theorem assert_nn (α : Assignment) (p q : ℕ) :
(Gate.assert [.Neg p,.Neg q]).Holds α ↔ ¬(α p = true ∧ α q = true) := by
cases hp : α p <;> cases hq : α q <;> simp [Gate.Holds,satisfiesClause,satisfiesLiteral,hp,hq]
private theorem slotPresence_iff (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
(∀ f ∈ [0,3,8,13], α (port n t s f 0) = false) ↔
portInput α n t s = none ∧ slotRows α n t s = [] := by
rw [no_portInput_iff,no_slotRows_iff]
constructor
· intro h
refine ⟨h 0 (by simp),?_⟩
intro i hi
rcases (show i = 0 ∨ i = 1 ∨ i = 2 by omega) with rfl|rfl|rfl
all_goals apply h; decide
· rintro ⟨hInput,hRows⟩ f hf
simp only [List.mem_cons,List.not_mem_nil,or_false] at hf
rcases hf with rfl|rfl|rfl|rfl
· exact hInput
· exact hRows 0 (by decide)
· exact hRows 1 (by decide)
· exact hRows 2 (by decide)
theorem slotShapeGates_exact (α : Assignment) (n t : ℕ) :
(∀ g ∈ slotShapeGates n t, g.Holds α) ↔ SlotsWellFormed α n t := by
simp only [slotShapeGates,slotGuardGates,List.forall_mem_flatMap,List.forall_mem_append,
List.forall_mem_map,assert_pn,assert_nn,List.mem_filter,List.mem_range,decide_eq_true_eq]
rw [SlotsWellFormed,liveSlots_disjoint_iff]
constructor
· intro h
refine ⟨?_,?_⟩
· intro s hs j hSmall hLarge
exact (h s hs).2 j ⟨Nat.lt_succ_of_le hLarge,hSmall⟩
· intro s hs hOff
exact (slotPresence_iff α n t s).mp (fun f hf => (h s hs).1 f hf hOff)
· rintro ⟨hDisj,hOff⟩ s hs
refine ⟨?_,?_⟩
· intro f hf he
exact (slotPresence_iff α n t s).mpr (hOff s hs he) f hf
· intro j hj
exact hDisj s hs j hj.2 (Nat.le_of_lt_succ hj.1)
theorem slotShapeGates_shared {n t : ℕ} {g : Gate} (hg : g ∈ slotShapeGates n t)
{r : ℕ} (hr : r ∈ Gate.names g) : r < sharedLimit n t := by
have hPort {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {f : ℕ} (hf : f < 19) :
port n t s f 0 < sharedLimit n t := by
obtain ⟨ha,hj,_⟩ := layout_mem.mp hs
exact port_lt_shared ha hj hf (Nat.two_pow_pos _)
obtain ⟨s,hs,hg⟩ := List.mem_flatMap.mp hg
rcases List.mem_append.mp hg with hg|hg
· obtain ⟨f,hf,rfl⟩ := List.mem_map.mp hg
have hF : f < 19 := by simp at hf; omega
simp only [Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,List.not_mem_nil,or_false] at hr
rcases hr with rfl|rfl
· exact hPort hs (by decide)
· exact hPort hs hF
· obtain ⟨j,hj,rfl⟩ := List.mem_map.mp hg
have hj' : j ≤ layoutHeight t := Nat.le_of_lt_succ (List.mem_range.mp (List.mem_filter.mp hj).1)
simp only [Gate.names,List.map_cons,List.map_nil,Literal.var,List.mem_cons,List.not_mem_nil,or_false] at hr
rcases hr with rfl|rfl
· exact hPort hs (by decide)
· exact hPort (ancestorAt_mem hs hj') (by decide)
theorem length_slotShapeGates (n t : ℕ) :
(slotShapeGates n t).length ≤ 2*layoutHorizon t*(layoutHeight t+5) := by
have hlen (slots : List (ℕ × ℕ)) : (slots.flatMap (slotGuardGates n t)).length ≤
slots.length * (layoutHeight t+5) := by
induction slots with
| nil => simp
| cons s slots ih =>
have heg := List.length_filter_le (fun j => decide (s.2 < j)) (List.range (layoutHeight t+1))
simp only [List.length_range] at heg
simp only [List.flatMap_cons,List.length_append, List.length_cons,Nat.add_mul,Nat.one_mul]
refine Nat.add_le_add ?_ ih |>.trans_eq (Nat.add_comm _ _)
simp only [slotGuardGates,List.length_append,List.length_map,List.length_cons,List.length_nil]
omega
exact (hlen _).trans (Nat.mul_le_mul_right _ (layoutSlots_length_le t))
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
open scoped BigOperators
private def slotPairEnc : (ℕ × ℕ) ↪ List Bool := encPair encUnary encUnary
theorem slotPort_poly {A : Type} {e : A ↪ List Bool} {n t a j f b : A → ℕ}
(hN : ComputableTidilyInPolyTime n e encUnary) (hT : ComputableTidilyInPolyTime t e encUnary)
(ha : ComputableTidilyInPolyTime a e encUnary) (hj : ComputableTidilyInPolyTime j e encUnary)
(hf : ComputableTidilyInPolyTime f e encUnary) (hb : ComputableTidilyInPolyTime b e encUnary) :
ComputableTidilyInPolyTime (fun x => port (n x) (t x) (a x,j x) (f x) (b x)) e encUnary := by
have hH := layoutHeight_poly.comp hT
have hW := layoutHorizon_poly.comp hT
unfold port
dsimp
fun_prop
private theorem slotGuardClause_poly {A : Type} {e : A ↪ List Bool} {r s : A → ℕ} (b : Bool)
(hr : ComputableTidilyInPolyTime r e encUnary)
(hs : ComputableTidilyInPolyTime s e encUnary) :
ComputableTidilyInPolyTime
(fun a => Gate.assert [if b then .Pos (r a) else .Neg (r a),.Neg (s a)]) e gateEnc := by
have hR := unary_mul.comp ((const 2).prod hr)
have hS := unary_mul.comp ((const 2).prod hs)
apply gate_assert
cases b
· exact cons' hR (cons' hS (const []))
· exact cons' (unary_add.comp (hR.prod (const 1))) (cons' hS (const []))
/-- Uniformly list the local shared-port checks. Ancestor powers are capped outside
the enumerated range, which keeps auxiliary unary computations polynomial. -/
theorem slotShapeGates_poly {A : Type} {e : A ↪ List Bool} {n t : A → ℕ}
(hN : ComputableTidilyInPolyTime n e encUnary) (hT : ComputableTidilyInPolyTime t e encUnary) :
ComputableTidilyInPolyTime (fun a => slotShapeGates (n a) (t a)) e (encList gateEnc) := by
let ep := encPair e slotPairEnc
let ef := encPair ep encUnary
have hX := fst e slotPairEnc
have hStart := (fst encUnary encUnary).comp (snd e slotPairEnc)
have hLevel := (snd encUnary encUnary).comp (snd e slotPairEnc)
have hN' := hN.comp hX
have hT' := hT.comp hX
have hHt := layoutHeight_poly.comp hT'
have hD := fst ep encUnary
have hI := snd ep encUnary
have hNt := hN'.comp hD
have hTt := hT'.comp hD
have hAt := hStart.comp hD
have hJt := hLevel.comp hD
have hLive := slotPort_poly hNt hTt hAt hJt (const 18) (const 0)
have hUse := slotPort_poly hNt hTt hAt hJt hI (const 0)
have hPresence := slotGuardClause_poly true hLive hUse
have hInactive := mapWithInput (f := fun (p : A × (ℕ × ℕ)) f =>
Gate.assert [.Pos (port (n p.1) (t p.1) p.2 18 0),.Neg (port (n p.1) (t p.1) p.2 f 0)])
(const [0,3,8,13]) hPresence
have hCap := unary_min.comp (hI.prod (hHt.comp hD))
have hw : ComputableTidilyInPolyTime (fun p : (A × (ℕ × ℕ)) × ℕ =>
2^(min p.2 (layoutHeight (t p.1.1)))) ef encUnary :=
unary_pow2_of_bound hCap (layoutHorizon_poly.comp hTt)
(fun p => Nat.pow_le_pow_right (by decide) (min_le_right _ _))
have hA' := unary_mul.comp ((unary_div_poly.comp (hAt.prod hw)).prod hw)
have hAncestor := slotPort_poly hNt hTt hA' hI (const 18) (const 0)
have hNoOverlap := slotGuardClause_poly false hLive hAncestor
have hCandidates := filterWithInput
(test := fun (p : A × (ℕ × ℕ)) j => decide (p.2.2 < j))
(range.comp (unary_add.comp (hHt.prod (const 1)))) (unary_lt' hJt hI)
let guard (p : A × (ℕ × ℕ)) (j : ℕ) := Gate.assert
[.Neg (port (n p.1) (t p.1) p.2 18 0),
.Neg (port (n p.1) (t p.1) (p.2.1 / 2^(min j (layoutHeight (t p.1))) *
2^(min j (layoutHeight (t p.1))),j) 18 0)]
have hSafe : ComputableTidilyInPolyTime (fun p : (A × (ℕ × ℕ)) × ℕ => guard p.1 p.2)
ef gateEnc := hNoOverlap
have hDisjoint := mapWithInput (f := guard) hCandidates hSafe
have hs := listAppend' hInactive hDisjoint
have hs' : ComputableTidilyInPolyTime (fun p : A × (ℕ × ℕ) => slotGuardGates (n p.1) (t p.1) p.2)
ep (encList gateEnc) := by
refine hs.of_enc_eq ?_
intro p
apply congrArg (encList gateEnc)
unfold slotGuardGates
congr 1
apply List.map_congr_left
intro j hj
have hJ : j ≤ layoutHeight (t p.1) := Nat.le_of_lt_succ (List.mem_range.mp (List.mem_filter.mp hj).1)
simp only [guard,ancestorAt,min_eq_left hJ]
exact flatMapWithInput (f := fun a s => slotGuardGates (n a) (t a) s)
(layoutSlots_poly.comp hT) hs'
theorem slotShapeGates_extends (n t : ℕ) (α : Assignment) :
ExtendsWith (sharedLimit n t) (slotShapeGates n t) α ↔ SlotsWellFormed α n t := by
rw [← slotShapeGates_exact]
constructor
· rintro ⟨β,h,hG⟩ g hg
exact (gate_congr g fun r hr => h r (slotShapeGates_shared hg hr)).1 (hG g hg)
· intro h
exact ⟨α,fun _ _ => rfl,h⟩
theorem layoutHeight_le_size (t : ℕ) : layoutHeight t ≤ t.size+6 := by
change (4*(9*t+1)-1).size ≤ t.size+6
apply Nat.size_le.mpr
have h := Nat.lt_size_self t
rw [pow_add]
norm_num
omega
theorem length_slotShapeGates_log (n t : ℕ) :
(slotShapeGates n t).length ≤ 1584*(t+1)*(t.size+1) := by
have hHor : layoutHorizon t ≤ 8*(9*t+1) := by
change slotWidth (4*(9*t+1)) ≤ 8*(9*t+1)
have h := slotWidth_le_double (cost := 4*(9*t+1)) (by omega)
omega
have hA : 2*layoutHorizon t ≤ 144*(t+1) := by omega
have hH := layoutHeight_le_size t
have hB : layoutHeight t+5 ≤ 11*(t.size+1) := by omega
exact (length_slotShapeGates n t).trans (calc
_ ≤ (144*(t+1))*(11*(t.size+1)) := Nat.mul_le_mul hA hB
_ = 1584*(t+1)*(t.size+1) := by ring)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
private theorem slotCenter_mod {t j : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t)
(hj : j ≤ s.2) : slotCenter s % 2^j = 0 := by
have hsDiv : 2^s.2 ∣ s.1 := Nat.dvd_iff_mod_eq_zero.mpr (layout_mem.mp hs).2.2
have hPow : 2^j ∣ 2^s.2 := Nat.pow_dvd_pow 2 hj
have hDiv := hPow.trans hsDiv
unfold slotCenter
exact Nat.dvd_iff_mod_eq_zero.mp (Nat.dvd_add (hDiv.mul_left 2) hPow)
private theorem div_eq_iff_of_mod_zero {a b w : ℕ} (ha : a%w=0) (hb : b%w=0) :
a / w = b / w ↔ a=b := by
have h₁ := Nat.mod_add_div a w
have h₂ := Nat.mod_add_div b w
rw [ha,Nat.zero_add] at h₁
rw [hb,Nat.zero_add] at h₂
constructor
· intro h
rw [h] at h₁
exact h₁.symm.trans h₂
· intro h
subst b
rfl
/-- A tier of width `2^j` can only receive rows from the slots at least that wide.
Their number is bounded simultaneously for every level. -/
theorem slotsAtLeast_bound (t j : ℕ) :
((layoutSlots t).filter fun s => j ≤ s.2).length ≤ (2*layoutHorizon t)/2^j := by
let xs := (layoutSlots t).filter fun s => j ≤ s.2
by_cases hj : j ≤ layoutHeight t
· have hMod : (2*layoutHorizon t) % 2^j = 0 :=
Nat.dvd_iff_mod_eq_zero.mp ((Nat.pow_dvd_pow 2 hj).mul_left 2)
let key (s : ℕ × ℕ) := slotCenter s/2^j
have keyND : (xs.map key).Nodup := by
apply ((layout_nodup t).filter _).map_on
intro a ha b hb he
obtain ⟨ha,hjA⟩ := List.mem_filter.mp ha
obtain ⟨hb,hjB⟩ := List.mem_filter.mp hb
exact slotCenter_injOn t ha hb
((div_eq_iff_of_mod_zero (slotCenter_mod ha (of_decide_eq_true hjA))
(slotCenter_mod hb (of_decide_eq_true hjB))).mp he)
have hSub : xs.map key ⊆ List.range ((2*layoutHorizon t)/2^j) := by
intro y hy
obtain ⟨s,hs,rfl⟩ := List.mem_map.mp hy
have hLt := slotCenter_lt t (List.mem_filter.mp hs).1
have hExact := Nat.mod_add_div (2*layoutHorizon t) (2^j)
rw [hMod,Nat.zero_add] at hExact
apply List.mem_range.mpr
apply (Nat.div_lt_iff_lt_mul (Nat.two_pow_pos j)).mpr
rwa [Nat.mul_comm,hExact]
simpa [xs] using keyND.length_le_of_subset hSub
· have hE : xs = [] := by
apply List.filter_eq_nil_iff.mpr
intro s hs
have hL := (layout_mem.mp hs).2.1
have hO : ¬ j ≤ s.2 := by omega
simp [hO]
change xs.length ≤ _
rw [hE]
simp
private theorem aligned_slot_end {t : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) :
s.1+2^s.2 ≤ layoutHorizon t := by
obtain ⟨ha,hl,hdiv⟩ := layout_mem.mp hs
have hMod : layoutHorizon t % 2^s.2 = 0 :=
Nat.dvd_iff_mod_eq_zero.mp (Nat.pow_dvd_pow 2 hl)
have hA := Nat.mod_add_div s.1 (2^s.2)
have hB := Nat.mod_add_div (layoutHorizon t) (2^s.2)
rw [hdiv,Nat.zero_add] at hA
rw [hMod,Nat.zero_add] at hB
have hQ : s.1/2^s.2 < layoutHorizon t/2^s.2 :=
Nat.lt_of_mul_lt_mul_left (by rwa [hA,hB])
have h := Nat.mul_le_mul_left (2^s.2) hQ
rwa [Nat.succ_eq_add_one,Nat.mul_add,Nat.mul_one,hA,hB] at h
private def slotCells (t : ℕ) (s : ℕ × ℕ) : List ℕ :=
(List.range (2^s.2)).map (fun i => s.2*layoutHorizon t+(s.1+i))
private theorem cells_div {t : ℕ} {s : ℕ × ℕ} (hs : s ∈ layoutSlots t) {i : ℕ} (hi : i < 2^s.2) :
(s.2*layoutHorizon t+(s.1+i))/layoutHorizon t = s.2 := by
have hEnd := aligned_slot_end hs
apply Nat.div_eq_of_lt_le
· exact Nat.le_add_right _ _
· rw [Nat.add_mul,Nat.one_mul]
omega
private theorem slotCells_disjoint {t : ℕ} {s r : ℕ × ℕ}
(hs : s ∈ layoutSlots t) (hr : r ∈ layoutSlots t) (hNe : s≠r)
{k : ℕ} (hk : k ∈ slotCells t s) : k ∉ slotCells t r := by
intro hk'
obtain ⟨i,hi,he⟩ := List.mem_map.mp hk
obtain ⟨j,hj,he'⟩ := List.mem_map.mp hk'
have hi' := List.mem_range.mp hi
have hj' := List.mem_range.mp hj
have hEq := he.trans he'.symm
have hLev : s.2=r.2 := by
rw [← cells_div hs hi', ← cells_div hr hj',hEq]
have hEqual : s.1+i = r.1+j := by rw [hLev] at hEq; omega
have ha := (layout_mem.mp hs).2.2
have hb := (layout_mem.mp hr).2.2
rw [← hLev] at hb hj'
have hs' : (s.1+i)/2^s.2 = s.1/2^s.2 := by
have hA := Nat.mod_add_div s.1 (2^s.2)
rw [ha,Nat.zero_add,Nat.mul_comm] at hA
apply Nat.div_eq_of_lt_le
· rw [hA]; omega
· rw [Nat.add_mul,Nat.one_mul,hA]; omega
have hr' : (r.1+j)/2^s.2 = r.1/2^s.2 := by
have hA := Nat.mod_add_div r.1 (2^s.2)
rw [hb,Nat.zero_add,Nat.mul_comm] at hA
apply Nat.div_eq_of_lt_le
· rw [hA]; omega
· rw [Nat.add_mul,Nat.one_mul,hA]; omega
have hAdd : s.1=r.1 := (div_eq_iff_of_mod_zero ha hb).mp (by rw [← hs',← hr',hEqual])
exact hNe (Prod.ext hAdd hLev)
/-- Counting all allocated columns, one horizon per width level suffices. -/
theorem layoutSlotBits_bound (t : ℕ) :
((layoutSlots t).map (fun s => 2^s.2)).sum ≤ (layoutHeight t+1)*layoutHorizon t := by
let cells := (layoutSlots t).flatMap (slotCells t)
have hLen (xs : List (ℕ × ℕ)) :
(xs.flatMap (slotCells t)).length = (xs.map (fun s => 2^s.2)).sum := by
induction xs with
| nil => rfl
| cons s xs ih => simp [slotCells,ih]
have hSub : cells ⊆ List.range ((layoutHeight t+1)*layoutHorizon t) := by
intro k hk
obtain ⟨s,hs,hk⟩ := List.mem_flatMap.mp hk
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hk
apply List.mem_range.mpr
have hEnd := aligned_slot_end hs
have hI := List.mem_range.mp hi
have hL := (layout_mem.mp hs).2.1
have hTop : (s.2+1)*layoutHorizon t ≤ (layoutHeight t+1)*layoutHorizon t :=
Nat.mul_le_mul_right _ (Nat.succ_le_succ hL)
rw [Nat.add_mul,Nat.one_mul] at hTop
omega
have hND : cells.Nodup := by
unfold cells List.Nodup
rw [List.pairwise_flatMap]
refine ⟨?_,?_⟩
· intro s _
unfold slotCells
apply List.Nodup.map
· intro a b h
dsimp only at h
omega
· exact List.nodup_range
· apply (layout_nodup t).imp_of_mem
intro s r hs hr hn a ha b hb he
subst b
exact slotCells_disjoint hs hr hn ha hb
have hBound := hND.length_le_of_subset hSub
simpa only [cells,hLen,List.length_range] using hBound
end CNFEncComplexity.Robson
namespace CNFEncComplexity.RobsonCNF
open CookLevin
/-- Select at least one guarded set of gate obligations. A satisfying branch
can use any auxiliary assignment while disabled branches impose no conditions. -/
def choiceGates (branches : List (ℕ × List Gate)) : List Gate :=
.assert (branches.map (fun b => Literal.Pos b.1)) ::
branches.flatMap (fun b => guarded (.Pos b.1) b.2)
theorem choiceGates_exact (branches : List (ℕ × List Gate)) (a : Assignment) :
(∀ g ∈ choiceGates branches, g.Holds a) ↔
(∃ b ∈ branches, a b.1=true) ∧
∀ b ∈ branches, a b.1=true → ∀ g ∈ b.2, g.Holds a := by
constructor
· intro h
have hHead := h (.assert (branches.map (fun b => Literal.Pos b.1))) List.mem_cons_self
change satisfiesClause a _ = true at hHead
obtain ⟨l,lMem,lSat⟩ := (satisfiesClause_iff a _).mp hHead
obtain ⟨b,bMem,rfl⟩ := List.mem_map.mp lMem
refine ⟨⟨b,bMem,lSat⟩,?_⟩
intro br hr he
apply (guarded_exact (.Pos br.1) br.2 a).mp _ he
intro g hg
exact h g (List.mem_cons_of_mem _ (List.mem_flatMap.mpr ⟨br,hr,hg⟩))
· rintro ⟨⟨b,hb,he⟩,h⟩ g hg
rcases List.mem_cons.mp hg with rfl | hg
· exact (satisfiesClause_iff a _).mpr ⟨.Pos b.1,List.mem_map.mpr ⟨b,hb,rfl⟩,he⟩
· obtain ⟨br,hbr,hg⟩ := List.mem_flatMap.mp hg
exact (guarded_exact (.Pos br.1) br.2 a).mpr (h br hbr) g hg
theorem choiceGates_sound (branches : List (ℕ × List Gate)) (a : Assignment)
(h : ∀ g ∈ choiceGates branches, g.Holds a) :
∃ b ∈ branches, ∀ g ∈ b.2, g.Holds a := by
obtain ⟨⟨b,hb,he⟩,hBody⟩ := (choiceGates_exact branches a).mp h
exact ⟨b,hb,hBody b hb he⟩
theorem choiceGates_complete (branches : List (ℕ × List Gate)) (a : Assignment)
(hDistinct : ∀ u ∈ branches, ∀ v ∈ branches, u.1=v.1 → u=v)
(b : ℕ × List Gate) (hb : b ∈ branches)
(hNoSelectors : ∀ g ∈ b.2, ∀ k ∈ g.names, k ∉ branches.map Prod.fst)
(hBody : ∀ g ∈ b.2, g.Holds a) :
∃ a' : Assignment, (∀ k ∉ branches.map Prod.fst, a' k = a k) ∧
∀ g ∈ choiceGates branches, g.Holds a' := by
let a' : Assignment := fun k =>
if k ∈ branches.map Prod.fst then decide (k=b.1) else a k
have keep (k : ℕ) (hk : k ∉ branches.map Prod.fst) : a' k = a k := by
simp [a',hk]
refine ⟨a',keep,(choiceGates_exact branches a').mpr ⟨?_,?_⟩⟩
· have hm : b.1 ∈ branches.map Prod.fst := List.mem_map_of_mem hb
exact ⟨b,hb,by simp only [a',if_pos hm,decide_true]⟩
· intro br hbr enable g hg
have hm : br.1 ∈ branches.map Prod.fst := List.mem_map_of_mem hbr
have hf : br.1=b.1 := by simpa only [a',if_pos hm,decide_eq_true_eq] using enable
have he : br=b := hDistinct br hbr b hb hf
subst br
exact (g.holds_congr a' a (fun k hk => keep k (hNoSelectors g hg k hk))).mpr (hBody g hg)
theorem choiceGates_length_le (branches : List (ℕ × List Gate)) :
(choiceGates branches).length ≤ 1+4*(branches.map fun b => b.2.length).sum := by
change (branches.flatMap (fun b => guarded (.Pos b.1) b.2)).length + 1 ≤ _
have aux (xs : List (ℕ × List Gate)) :
(xs.flatMap (fun b => guarded (.Pos b.1) b.2)).length ≤
4*(xs.map fun b => b.2.length).sum := by
induction xs with
| nil => simp
| cons b bs ih =>
simp only [List.flatMap_cons,List.length_append,List.map_cons,List.sum_cons,Nat.mul_add]
exact Nat.add_le_add (length_guarded (.Pos b.1) b.2) ih
have h := aux branches
omega
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open CookLevin
theorem wireValue_eq_bitString (α : Assignment) (key : ℕ → ℕ) (n : ℕ) :
wireValue α key n = (Cslib.BitString.equivFin n (fun i => α (key i.val))).val := by
rw [wireValue_eq_sum,Cslib.BitString.val_equivFin_eq_sum]
rw [← List.sum_toFinset _ List.nodup_range,List.toFinset_range,Finset.sum_range]
theorem wireValue_eq_iff (α : Assignment) (lhs rhs : ℕ → ℕ) (n : ℕ) :
wireValue α lhs n = wireValue α rhs n ↔ ∀ i < n, α (lhs i) = α (rhs i) := by
rw [wireValue_eq_bitString,wireValue_eq_bitString]
constructor
· intro h i hi
have hh := (Cslib.BitString.equivFin n).injective (Fin.ext h)
exact congrFun hh ⟨i,hi⟩
· intro h
have hh : (fun i : Fin n => α (lhs i.val)) = (fun i : Fin n => α (rhs i.val)) :=
funext (fun i => h _ i.isLt)
rw [hh]
/-- Require two little-endian words to be equal without introducing auxiliary wires. -/
def wordCopy (n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
(List.range n).map (fun i => .copy (lhs i) (rhs i))
@[simp] theorem length_wordCopy (n : ℕ) (lhs rhs : ℕ → ℕ) :
(wordCopy n lhs rhs).length = n := by simp [wordCopy]
theorem wordCopy_exact (n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment) :
(∀ g ∈ wordCopy n lhs rhs, g.Holds α) ↔ wireValue α lhs n = wireValue α rhs n := by
rw [wireValue_eq_iff]
constructor
· intro h i hi
exact h (.copy (lhs i) (rhs i)) (List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩)
· intro h g hg
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
exact h i (List.mem_range.mp hi)
/-- Pin a binary word to a known natural value. -/
def wordConst (n : ℕ) (key : ℕ → ℕ) (value : ℕ) : List Gate :=
(List.range n).map (fun i => .pin (key i) (value.testBit i))
@[simp] theorem length_wordConst (n : ℕ) (key : ℕ → ℕ) (value : ℕ) :
(wordConst n key value).length = n := by simp [wordConst]
theorem wordConst_exact (n : ℕ) (key : ℕ → ℕ) (value : ℕ) (hv : value < 2^n)
(α : Assignment) :
(∀ g ∈ wordConst n key value, g.Holds α) ↔ wireValue α key n = value := by
let b : Fin (2^n) := ⟨value,hv⟩
let e := Cslib.BitString.equivFin n
rw [wireValue_eq_bitString]
change (∀ g ∈ wordConst n key value,g.Holds α) ↔ (e (fun i => α (key i.val))).val = b.val
constructor
· intro h
have he : (fun i : Fin n => α (key i.val)) = e.symm b := by
funext i
change α (key i.val) = (Cslib.BitString.equivFin n).symm b i
rw [Cslib.BitString.equivFin_symm_apply]
exact h (.pin (key i.val) (b.val.testBit i.val)) (List.mem_map.mpr ⟨_,List.mem_range.mpr i.isLt,rfl⟩)
rw [he,e.apply_symm_apply]
· intro h g hg
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hf := congrArg e.symm (Fin.ext h)
rw [e.symm_apply_apply] at hf
have hs := congrFun hf ⟨i,List.mem_range.mp hi⟩
change α (key i) = value.testBit i
change α (key i) = (Cslib.BitString.equivFin n).symm b ⟨i,List.mem_range.mp hi⟩ at hs
rw [Cslib.BitString.equivFin_symm_apply] at hs
exact hs
def mismatchWire (base i : ℕ) := base+i
/-- To witness disequality, compute each difference bit and assert their disjunction. -/
def wordMismatch (base n : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
(List.range n).map (fun i => .parity (mismatchWire base i) (lhs i) (rhs i)) ++
[.assert ((List.range n).map (fun i => .Pos (mismatchWire base i)))]
@[simp] theorem length_wordMismatch (base n : ℕ) (lhs rhs : ℕ → ℕ) :
(wordMismatch base n lhs rhs).length = n+1 := by simp [wordMismatch]
theorem wordMismatch_exact (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(h : ∀ g ∈ wordMismatch base n lhs rhs, g.Holds α) :
wireValue α lhs n ≠ wireValue α rhs n := by
intro he
have hSame := (wireValue_eq_iff α lhs rhs n).mp he
have hg := h (.assert ((List.range n).map (fun i => .Pos (mismatchWire base i))))
(List.mem_append.mpr (.inr List.mem_cons_self))
change satisfiesClause α _ = true at hg
obtain ⟨lit,hlit,ht⟩ := (satisfiesClause_iff α _).mp hg
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hlit
have hb : α (mismatchWire base i) = (α (lhs i) ^^ α (rhs i)) :=
h (.parity (mismatchWire base i) (lhs i) (rhs i))
(List.mem_append.mpr (.inl (List.mem_map.mpr ⟨i,hi,rfl⟩)))
change α (mismatchWire base i) = true at ht
rw [hb,hSame i (List.mem_range.mp hi)] at ht
cases heq : α (rhs i) <;> simp [heq] at ht
theorem wordMismatch_extends (base n : ℕ) (lhs rhs : ℕ → ℕ) (α : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base)
(h : wireValue α lhs n ≠ wireValue α rhs n) :
∃ β : Assignment, (∀ k, (k < base ∨ base+n ≤ k) → β k = α k) ∧
(∀ g ∈ wordMismatch base n lhs rhs,g.Holds β) := by
let β : Assignment := fun k =>
if base ≤ k ∧ k < base+n then α (lhs (k-base)) ^^ α (rhs (k-base)) else α k
have hSmall (k : ℕ) (hk : k < base) : β k = α k := by
have hx : ¬(base ≤ k ∧ k < base+n) := fun hp => (Nat.not_le_of_gt hk) hp.1
simp [β,hx]
have hBit (i : ℕ) (hi : i < n) : β (mismatchWire base i) = (α (lhs i) ^^ α (rhs i)) := by
have hh : base ≤ base+i ∧ base+i < base+n := by omega
simp [β,mismatchWire,hh]
have hWitness : ∃ i < n, α (lhs i) ≠ α (rhs i) := by
by_contra hn
apply h
apply (wireValue_eq_iff α lhs rhs n).mpr
intro i hi
by_contra hh
exact hn ⟨i,hi,hh⟩
refine ⟨β,?_,?_⟩
· intro k hk
rcases hk with hk | hk
· exact hSmall k hk
· have hx : ¬(base ≤ k ∧ k < base+n) := fun hp => (Nat.not_lt_of_ge hk) hp.2
simp [β,hx]
· intro g hg
rcases List.mem_append.mp hg with hg | hg
· obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hg
have hI := List.mem_range.mp hi
change β (mismatchWire base i) = (β (lhs i) ^^ β (rhs i))
rw [hBit i hI,hSmall _ (hL i hI),hSmall _ (hR i hI)]
· rw [List.mem_singleton] at hg
subst g
apply (satisfiesClause_iff β _).mpr
obtain ⟨i,hi,hdiff⟩ := hWitness
refine ⟨.Pos (mismatchWire base i),List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩,?_⟩
change β (mismatchWire base i) = true
rw [hBit i hi]
cases ha : α (lhs i) <;> cases hb : α (rhs i) <;> simp_all
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
inductive PacketExpr where
| constant (n : ℕ)
| operand (i : ℕ)
| symbol
| add (a b : PacketExpr)
| sub (a b : PacketExpr)
| width (a : PacketExpr)
def PacketExpr.eval (p : Packet) : PacketExpr → ℕ
| .constant n => n
| .operand i => p.operand i
| .symbol => p.input.getD 0
| .add a b => a.eval p + b.eval p
| .sub a b => a.eval p - b.eval p
| .width a => bitLen (a.eval p)
structure PacketAccessPattern where
writes : Bool
address : PacketExpr
value : PacketExpr
def PacketAccessPattern.eval (p : Packet) (a : PacketAccessPattern) : MemoryAccess :=
⟨a.address.eval p,a.value.eval p,a.writes⟩
structure PacketPattern where
next : ℕ
readsInput : Bool
accesses : List PacketAccessPattern
cost : PacketExpr
zero : Option Bool := none
def PacketPattern.matches (m : PacketPattern) (next : ℕ) (p : Packet) : Prop :=
next=m.next ∧ p =
⟨if m.readsInput then some (PacketExpr.eval p .symbol) else none,
m.accesses.map (PacketAccessPattern.eval p),m.cost.eval p⟩ ∧
∀ flag, m.zero = some flag → (p.operand 0=0 ↔ flag=true)
private def a : PacketExpr := .operand 0
private def b : PacketExpr := .operand 1
private def sym : PacketExpr := .symbol
private def k : ℕ → PacketExpr := PacketExpr.constant
private def c1 (x : PacketExpr) : PacketExpr := .add (.constant 1) (.width x)
private def c2 (x y : PacketExpr) : PacketExpr := .add (c1 x) (.width y)
private def c3 (x y z : PacketExpr) : PacketExpr := .add (c2 x y) (.width z)
private def rd (i v : PacketExpr) : PacketAccessPattern := ⟨false,i,v⟩
private def wr (i v : PacketExpr) : PacketAccessPattern := ⟨true,i,v⟩
/-- Every instruction has one or two conjunctions of fixed packet tests.
Reading an input checks that its symbol exists and copies the two raw bits. -/
def instrPatterns (pc : ℕ) : Instr → List PacketPattern
| .loadc v => [⟨pc+1,false,[wr (k 0) (k v)],c1 (k v),none⟩]
| .load j => [⟨pc+1,false,[rd (k j) a,wr (k 0) a],c2 (k j) a,none⟩]
| .loadi j => [⟨pc+1,false,[rd (k j) a,rd a b,wr (k 0) b],c3 (k j) a b,none⟩]
| .store j => [⟨pc+1,false,[rd (k 0) a,wr (k j) a],c2 (k j) a,none⟩]
| .storei j => [⟨pc+1,false,[rd (k j) a,rd (k 0) b,wr a b],c3 (k j) a b,none⟩]
| .add j => [⟨pc+1,false,[rd (k 0) a,rd (k j) b,wr (k 0) (.add a b)],c3 (k j) a b,none⟩]
| .sub j => [⟨pc+1,false,[rd (k 0) a,rd (k j) b,wr (k 0) (.sub a b)],c3 (k j) a b,none⟩]
| .read => [⟨pc+1,true,[wr (k 0) sym],c1 sym,none⟩]
| .jump j => [⟨j,false,[],c1 (k j),none⟩]
| .jzero j =>
[⟨j,false,[rd (k 0) (k 0)],c2 (k j) (k 0),some true⟩,
⟨pc+1,false,[rd (k 0) a],c2 (k j) a,some false⟩]
| .njump l r => [⟨l,false,[],c2 (k l) (k r),none⟩,⟨r,false,[],c2 (k l) (k r),none⟩]
| .halt => []
theorem instrPatterns_length (pc : ℕ) (op : Instr) : (instrPatterns pc op).length ≤ 2 := by
cases op <;> simp [instrPatterns]
theorem instrPatterns_exact (op : Instr) (pc next : ℕ) (p : Packet) :
InstrPacket op pc next p ↔ ∃ m ∈ instrPatterns pc op, m.matches next p := by
cases op <;> simp [InstrPacket,instrPatterns,PacketPattern.matches,PacketExpr.eval,
PacketAccessPattern.eval,a,b,sym,k,c1,c2,c3,rd,wr,MemoryAccess.read,MemoryAccess.write]
· by_cases h : p.operand 0=0 <;> simp [h]
· tauto
inductive AdvancePattern where
| idle
| stop (pc : ℕ)
| step (pc : ℕ) (p : PacketPattern)
def AdvancePattern.matches (v : Option PortView) (u w : ScanState) : AdvancePattern → Prop
| .idle => v=none ∧ u=w
| .stop pc => v=some finalPacket.ports ∧ u.control=some pc ∧ w.control=none ∧
w.clock=u.clock+(1+bitLen 1)
| .step pc p => ∃ x next, v=some x ∧ u.control=some pc ∧ w.control=some next ∧
u.clock ≤ w.clock ∧ p.matches next ⟨x.1,x.2,w.clock-u.clock⟩
def opcodePatterns (pc : ℕ) (op : Instr) : List AdvancePattern :=
match op with
| .halt => [.stop pc]
| _ => (instrPatterns pc op).map (.step pc)
def advancePatterns (prog : List Instr) : List AdvancePattern :=
.idle :: (List.finRange prog.length).flatMap
(fun i => opcodePatterns i.val prog[i.val])
private theorem opcodePatterns_step {pc : ℕ} {op : Instr} {pat : PacketPattern} :
AdvancePattern.step pc pat ∈ opcodePatterns pc op ↔ pat ∈ instrPatterns pc op := by
cases op <;> simp [opcodePatterns,instrPatterns]
private theorem opcodePatterns_cases {pc : ℕ} {op : Instr} {pat : AdvancePattern}
(h : pat ∈ opcodePatterns pc op) :
(op = .halt ∧ pat = .stop pc) ∨ ∃ m ∈ instrPatterns pc op, pat = .step pc m := by
cases op <;> simp_all [opcodePatterns,List.mem_map] <;> aesop
theorem advancePatterns_length (prog : List Instr) : (advancePatterns prog).length ≤ 1+2*prog.length := by
have hOp (pc : ℕ) (op : Instr) : (opcodePatterns pc op).length ≤ 2 := by
cases op <;> simp [opcodePatterns,instrPatterns]
have hRows (xs : List (Fin prog.length)) :
(xs.flatMap (fun i => opcodePatterns i.val prog[i.val])).length ≤ 2*xs.length := by
induction xs with
| nil => simp
| cons i xs ih =>
simp only [List.flatMap_cons,List.length_append,List.length_cons,Nat.mul_add,Nat.mul_one]
have h := hOp i.val prog[i.val]
omega
have h := hRows (List.finRange prog.length)
simp only [advancePatterns,List.length_cons,List.length_finRange] at *
omega
theorem advancePatterns_exact (prog : List Instr) (v : Option PortView) (u w : ScanState) :
LocalAdvance prog v u w ↔ ∃ pat ∈ advancePatterns prog, pat.matches v u w := by
have atOp {pc : ℕ} {op : Instr} (h : prog[pc]? = some op) :
∃ i : Fin prog.length, i.val=pc ∧ prog[i.val]=op := by
obtain ⟨hi,he⟩ := List.getElem?_eq_some_iff.mp h
exact ⟨⟨pc,hi⟩,rfl,he⟩
have emit {pc : ℕ} {op : Instr} {pat : AdvancePattern}
(hOp : prog[pc]? = some op) (hPat : pat ∈ opcodePatterns pc op) :
pat ∈ advancePatterns prog := by
obtain ⟨i,hi,he⟩ := atOp hOp
apply List.mem_cons_of_mem
apply List.mem_flatMap.mpr
refine ⟨i,List.mem_finRange i,?_⟩
rwa [he,hi]
constructor
· intro h
cases v with
| none =>
exact ⟨.idle,List.mem_cons_self,rfl,h⟩
| some x =>
cases hu : u.control with
| none => simp [LocalAdvance,hu] at h
| some pc =>
cases hw : w.control with
| none =>
have hh : prog[pc]? = some .halt ∧ x = finalPacket.ports ∧
w.clock = u.clock+(1+bitLen 1) := by simpa [LocalAdvance,hu,hw] using h
exact ⟨.stop pc,emit hh.1 (by simp [opcodePatterns]),congrArg some hh.2.1,hu,hw,hh.2.2⟩
| some next =>
have hh : u.clock ≤ w.clock ∧ ∃ op, prog[pc]? = some op ∧
InstrPacket op pc next ⟨x.1,x.2,w.clock-u.clock⟩ := by
simpa [LocalAdvance,hu,hw] using h
obtain ⟨op,hOp,hStep⟩ := hh.2
obtain ⟨m,hm,hRule⟩ := (instrPatterns_exact op pc next _).mp hStep
exact ⟨.step pc m,emit hOp (opcodePatterns_step.mpr hm),x,next,rfl,hu,hw,hh.1,hRule⟩
· rintro ⟨pat,hPat,hMatch⟩
rcases List.mem_cons.mp hPat with rfl | hPat
· obtain ⟨rfl,he⟩ := hMatch
simp [LocalAdvance,he]
· obtain ⟨i,_,hOpPat⟩ := List.mem_flatMap.mp hPat
have hOp : prog[i.val]? = some prog[i.val] :=
List.getElem?_eq_getElem i.isLt
rcases opcodePatterns_cases hOpPat with ⟨he,rfl⟩ | ⟨m,hm,rfl⟩
· obtain ⟨rfl,hu,hw,hClock⟩ := hMatch
simp [LocalAdvance,hu,hw,hOp,he,hClock]
· obtain ⟨x,next,rfl,hu,hw,hClock,hRule⟩ := hMatch
have hStep := (instrPatterns_exact _ _ _ _).mpr ⟨m,hm,hRule⟩
simpa only [LocalAdvance,hu,hw] using
And.intro hClock ⟨prog[i.val],hOp,hStep⟩
end CNFEncComplexity.Robson
namespace CNFEncComplexity.RobsonCNF
open CookLevin
/-- A too-wide constant makes only this branch impossible. -/
def boundedWordConst (n : ℕ) (key : ℕ → ℕ) (value : ℕ) : List Gate :=
if value < 2^n then wordConst n key value else [.assert []]
theorem boundedWordConst_exact (n : ℕ) (key : ℕ → ℕ) (c : ℕ) (a : Assignment) :
(∀ g ∈ boundedWordConst n key c, g.Holds a) ↔ wireValue a key n = c := by
by_cases h : c < 2^n
· simpa only [boundedWordConst,h,if_true] using wordConst_exact n key c h a
· have hnot : ¬ wireValue a key n = c := by
intro he
exact h (he ▸ wireValue_lt a key n)
simp [boundedWordConst,h,hnot,Gate.Holds,satisfiesClause]
theorem boundedWordConst_length (n : ℕ) (key : ℕ → ℕ) (c : ℕ) :
(boundedWordConst n key c).length ≤ n+1 := by
unfold boundedWordConst
split <;> simp
def paddedKey (n z : ℕ) (key : ℕ → ℕ) (i : ℕ) : ℕ := if i < n then key i else z
theorem wireValue_pad (a : Assignment) (n z : ℕ) (key : ℕ → ℕ)
(hz : a z=false) (m : ℕ) (hm : n ≤ m) :
wireValue a (paddedKey n z key) m = wireValue a key n := by
induction m,hm using Nat.le_induction with
| base =>
apply wireValue_key_congr
intro i hi
simp [paddedKey,hi]
| succ m hm ih =>
simpa [wireValue,paddedKey,show ¬ m < n by omega,hz] using ih
def paddedWordCopy (width leftWidth rightWidth z : ℕ) (lhs rhs : ℕ → ℕ) : List Gate :=
wordCopy width (paddedKey leftWidth z lhs) (paddedKey rightWidth z rhs)
theorem paddedWordCopy_exact (width n m z : ℕ) (lhs rhs : ℕ → ℕ) (a : Assignment)
(hn : n ≤ width) (hm : m ≤ width) (hz : a z=false) :
(∀ g ∈ paddedWordCopy width n m z lhs rhs,g.Holds a) ↔
wireValue a lhs n = wireValue a rhs m := by
rw [paddedWordCopy,wordCopy_exact,wireValue_pad a n z lhs hz width hn,
wireValue_pad a m z rhs hz width hm]
/-- The low sum bits match the supplied output word, and overflow is forbidden. -/
def exactSumGates (base n : ℕ) (lhs rhs out : ℕ → ℕ) : List Gate :=
rippleCircuit false base n lhs rhs ++
(.pin (rippleCarryWire base n) false :: wordCopy n out (rippleBitWire base))
theorem exactSumGates_length (base n : ℕ) (lhs rhs out : ℕ → ℕ) :
(exactSumGates base n lhs rhs out).length ≤ 8*n+2 := by
simp [exactSumGates,length_rippleCircuit]
omega
private theorem expandedSum (base n : ℕ) (lhs rhs : ℕ → ℕ) (a : Assignment)
(h : ∀ g ∈ rippleCircuit false base n lhs rhs,g.Holds a) :
wireValue a (rippleBitWire base) n +
(if a (rippleCarryWire base n) then 2^n else 0) =
wireValue a lhs n + wireValue a rhs n := by
have he := rippleCircuit_add_exact base n lhs rhs a h
have he' : wireValue a (addOutputWire base n) n = wireValue a (rippleBitWire base) n := by
apply wireValue_key_congr
intro i hi
simp [addOutputWire,hi]
simpa only [wireValue,he',addOutputWire,lt_irrefl,if_false] using he
theorem exactSumGates_sound (base n : ℕ) (lhs rhs out : ℕ → ℕ) (a : Assignment)
(h : ∀ g ∈ exactSumGates base n lhs rhs out,g.Holds a) :
wireValue a out n = wireValue a lhs n + wireValue a rhs n := by
rw [exactSumGates,List.forall_mem_append,List.forall_mem_cons] at h
obtain ⟨hr,hNo,hCopy⟩ := h
have hBits := (wordCopy_exact n out (rippleBitWire base) a).mp hCopy
have hSum := expandedSum base n lhs rhs a hr
change a (rippleCarryWire base n)=false at hNo
simpa [← hBits,hNo] using hSum
theorem exactSumGates_complete (base n : ℕ) (lhs rhs out : ℕ → ℕ) (a : Assignment)
(hL : ∀ i < n, lhs i < base) (hR : ∀ i < n, rhs i < base)
(hO : ∀ i < n, out i < base)
(hSum : wireValue a out n = wireValue a lhs n + wireValue a rhs n) :
∃ b : Assignment, (∀ k, (k < base ∨ base+8*n+1 ≤ k) → b k=a k) ∧
∀ g ∈ exactSumGates base n lhs rhs out,g.Holds b := by
obtain ⟨b,hKeep,hRipple⟩ := rippleCircuit_extends_interval false base n lhs rhs a hL hR
have hL' := wireValue_congr (α := b) (β := a) (fun i hi => hKeep _ (.inl (hL i hi)))
have hR' := wireValue_congr (α := b) (β := a) (fun i hi => hKeep _ (.inl (hR i hi)))
have hO' := wireValue_congr (α := b) (β := a) (fun i hi => hKeep _ (.inl (hO i hi)))
have hE := expandedSum base n lhs rhs b hRipple
rw [hL',hR',← hSum,← hO'] at hE
have hLt := wireValue_lt b out n
have hCarry : b (rippleCarryWire base n)=false := by
cases hb : b (rippleCarryWire base n)
· rfl
· simp [hb] at hE
omega
have hCopy : wireValue b out n = wireValue b (rippleBitWire base) n := by
simpa [hCarry] using hE.symm
exact ⟨b,hKeep,(List.forall_mem_append.mpr ⟨hRipple,List.forall_mem_cons.mpr
⟨hCarry,(wordCopy_exact n out (rippleBitWire base) b).mpr hCopy⟩⟩)⟩
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
/-- The three action lanes of a slot each carry a presence bit, a write flag,
and two words. The old value is supplied independently by the memory checker. -/
def slotRowPresent (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) : ℕ := port n t s (3+5*i) 0
def slotRowWrite (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) : ℕ := port n t s (3+5*i+1) 0
def slotRowAddress (n t : ℕ) (s : ℕ × ℕ) (i bit : ℕ) : ℕ := port n t s (3+5*i+2) bit
def slotRowValue (n t : ℕ) (s : ℕ × ℕ) (i bit : ℕ) : ℕ := port n t s (3+5*i+3) bit
def slotRawAction (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) (i : ℕ) : MemoryAccess :=
⟨wireValue a (slotRowAddress n t s i) (2^s.2),
wireValue a (slotRowValue n t s i) (2^s.2), a (slotRowWrite n t s i)⟩
theorem slotView_rawActions (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) :
(slotView a n t s).2 =
((List.range 3).filter fun i => a (slotRowPresent n t s i)).map (slotRawAction a n t s) := by
have hAction (i : ℕ) : (portMemory a n t s i).map ObservedAccess.action =
if a (slotRowPresent n t s i) then some (slotRawAction a n t s i) else none := by
unfold portMemory slotRowPresent
split <;> simp_all [slotRawAction,slotRowAddress,slotRowValue,slotRowWrite,
portWord,wireValue_eq_sum]
unfold slotView slotRows
rw [List.map_filterMap]
change (List.range 3).filterMap (fun i => (portMemory a n t s i).map ObservedAccess.action) = _
simp_rw [hAction]
induction List.range 3 with
| nil => rfl
| cons i is ih =>
cases hp : a (slotRowPresent n t s i) <;>
simp [hp,ih]
def physicalMask (key : ℕ) (i : ℕ) : Bool := key.testBit i
def maskLanes (key : ℕ) : List ℕ := (List.range 3).filter (physicalMask key)
theorem mask_exists (flags : ℕ → Bool) :
∃ k < 8, ∀ i < 3, flags i = physicalMask k i := by
have hEq (i : ℕ) (hi : i < 3) : i=0 ∨ i=1 ∨ i=2 := by omega
cases h0 : flags 0 <;> cases h1 : flags 1 <;> cases h2 : flags 2
· refine ⟨0,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp [h0,h1,h2,physicalMask]
· refine ⟨4,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
· refine ⟨2,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
· refine ⟨6,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
· refine ⟨1,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
· refine ⟨5,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
· refine ⟨3,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
· refine ⟨7,by decide,?_⟩
intro i hi
rcases hEq i hi with rfl | rfl | rfl <;> simp only [h0,h1,h2] <;> decide
/-- Four literal pins read guard availability and the static mask of physical lanes. -/
def slotPacketShape (n t : ℕ) (s : ℕ × ℕ) (readsInput : Bool) (mask : ℕ) : List Gate :=
.pin (port n t s 0 0) readsInput ::
(List.range 3).map (fun i => .pin (slotRowPresent n t s i) (physicalMask mask i))
theorem slotPacketShape_exact (a : Assignment) (n t : ℕ) (s : ℕ × ℕ)
(readsInput : Bool) (mask : ℕ) :
(∀ g ∈ slotPacketShape n t s readsInput mask,g.Holds a) ↔
a (port n t s 0 0) = readsInput ∧
∀ i < 3, a (slotRowPresent n t s i) = physicalMask mask i := by
rw [slotPacketShape,List.forall_mem_cons]
simp only [List.forall_mem_map,List.mem_range,Gate.Holds]
theorem slotPacketShape_view (a : Assignment) (n t : ℕ) (s : ℕ × ℕ)
(readsInput : Bool) (mask : ℕ) (h : ∀ g ∈ slotPacketShape n t s readsInput mask,g.Holds a) :
slotView a n t s =
(if readsInput then some ((a (port n t s 1 0)).toNat+2*(a (port n t s 2 0)).toNat)
else none,(maskLanes mask).map (slotRawAction a n t s)) := by
have hs := (slotPacketShape_exact a n t s readsInput mask).mp h
apply Prod.ext
· simp [slotView,portInput,hs.1]
· rw [slotView_rawActions,maskLanes]
congr 1
apply List.filter_congr
intro i hi
exact hs.2 i (List.mem_range.mp hi)
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
def programField (w : List (List Bool)) (pc field : ℕ) : List Bool :=
w.getD (2+3*pc+field) []
private theorem progWords_field (prog : List Instr) {pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) (f : ℕ) (hf : f < 3) :
(progWords prog).getD (3*pc+f) [] = (instrWords op).getD f [] := by
induction prog generalizing pc with
| nil => simp at hp
| cons p prog ih =>
cases pc with
| zero =>
have hEq : p=op := Option.some.inj hp
subst p
simpa only [progWords,List.flatMap_cons,Nat.mul_zero,Nat.zero_add] using
List.getD_append (instrWords op) (progWords prog) [] f (by simpa [instrWords] using hf)
| succ pc =>
rw [progWords,List.flatMap_cons,List.getD_eq_getElem?_getD,
List.getElem?_append_right (by simp [instrWords]; omega)]
have hNat : 3*(pc+1)+f-(instrWords p).length = 3*pc+f := by simp [instrWords]; omega
rw [hNat,← List.getD_eq_getElem?_getD]
exact ih hp
theorem programField_exact {prog : List Instr} {n t pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) {f : ℕ} (hf : f < 3) :
programField ([unaryWord n,unaryWord t] ++ progWords prog) pc f = (instrWords op).getD f [] := by
unfold programField
rw [List.getD_eq_getElem?_getD,List.getElem?_append_right (by simp; omega),List.length_cons,
List.length_cons,List.length_nil]
have h : 2+3*pc+f-(0+1+1) = 3*pc+f := by omega
rw [h,← List.getD_eq_getElem?_getD,progWords_field prog hp f hf]
theorem programField_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)} {pc field : A → ℕ}
(hw : ComputableTidilyInPolyTime ws e (encList encBits))
(hp : ComputableTidilyInPolyTime pc e encUnary)
(hf : ComputableTidilyInPolyTime field e encUnary) :
ComputableTidilyInPolyTime (fun a => programField (ws a) (pc a) (field a)) e encBits := by
have hx : ComputableTidilyInPolyTime (fun a => 2+3*pc a+field a) e encUnary := by fun_prop
exact (listGetD (encA := encBits) []).comp (hw.prod hx)
theorem program_opcode {prog : List Instr} {n t pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) :
(programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 0).length = instrTag op := by
rw [programField_exact hp (by decide)]
simp [instrWords,unaryWord,List.getD]
private theorem encodeNum_bits_aux (b : Bool) (n : Num) (h : n=0 → b=true) :
Computability.encodeNum (cond b Num.bit1 Num.bit0 n) = b :: Computability.encodeNum n := by
cases n with
| zero => have hB := h rfl; subst b; rfl
| pos v => cases b <;> rfl
theorem binWord_bits (n : ℕ) : binWord n = n.bits := by
induction n using Nat.binaryRec' with
| zero => rfl
| bit b n hBN ih =>
have hb : (Num.ofNat' n)=0 → b=true := by
intro h0
apply hBN
have hComp := congrArg (fun a : Num => (a : ℕ)) h0
simpa [Num.ofNat'_eq] using hComp
change Computability.encodeNum (↑(Nat.bit b n)) = (Nat.bit b n).bits
rw [← Num.ofNat'_eq,Num.ofNat'_bit,encodeNum_bits_aux b _ hb]
rw [Num.ofNat'_eq]
change b::binWord n = (Nat.bit b n).bits
rw [ih]
unfold Nat.bits
rw [Nat.binaryRec_eq]
exact Or.inr hBN
theorem program_first_arg {prog : List Instr} {n t pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) :
programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 1 = (instrArgs op).1.bits := by
rw [programField_exact hp (by decide)]
exact binWord_bits _
theorem program_second_arg {prog : List Instr} {n t pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) :
programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 2 = (instrArgs op).2.bits := by
rw [programField_exact hp (by decide)]
exact binWord_bits _
theorem program_opcode_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)} {pc : A → ℕ}
(hw : ComputableTidilyInPolyTime ws e (encList encBits))
(hp : ComputableTidilyInPolyTime pc e encUnary) :
ComputableTidilyInPolyTime (fun a => (programField (ws a) (pc a) 0).length) e encUnary :=
length_bits.comp (programField_poly hw hp (const 0))
theorem program_arg_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)} {pc field : A → ℕ}
(hw : ComputableTidilyInPolyTime ws e (encList encBits))
(hp : ComputableTidilyInPolyTime pc e encUnary)
(hf : ComputableTidilyInPolyTime field e encUnary) :
ComputableTidilyInPolyTime (fun a => ofBits (programField (ws a) (pc a) (field a))) e encNat :=
bitsToNat.comp (programField_poly hw hp hf)
theorem program_first_arg_nat {prog : List Instr} {n t pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) :
ofBits (programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 1) = (instrArgs op).1 := by
rw [program_first_arg hp]
exact Nat.foldr_bit_bits _
theorem program_second_arg_nat {prog : List Instr} {n t pc : ℕ} {op : Instr}
(hp : prog[pc]? = some op) :
ofBits (programField ([unaryWord n,unaryWord t] ++ progWords prog) pc 2) = (instrArgs op).2 := by
rw [program_second_arg hp]
exact Nat.foldr_bit_bits _
def programLength (w : List (List Bool)) : ℕ := (w.length-2)/3
theorem programLength_exact (prog : List Instr) (n t : ℕ) :
programLength ([unaryWord n,unaryWord t] ++ progWords prog) = prog.length := by
have hLength : (progWords prog).length = prog.length*3 := by
induction prog with
| nil => rfl
| cons p ps ih =>
simp only [progWords,List.flatMap_cons,List.length_append,instrWords,
List.length_cons,List.length_nil] at *
omega
unfold programLength
rw [List.length_append, hLength]
simp
theorem programLength_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)}
(hw : ComputableTidilyInPolyTime ws e (encList encBits)) :
ComputableTidilyInPolyTime (fun a => programLength (ws a)) e encUnary := by
exact unary_div_poly.comp ((unary_sub.comp (((length encBits).comp hw).prod (const 2))).prod (const 3))
theorem programArgSize_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)} {pc field : A → ℕ}
(hw : ComputableTidilyInPolyTime ws e (encList encBits))
(hp : ComputableTidilyInPolyTime pc e encUnary)
(hf : ComputableTidilyInPolyTime field e encUnary) :
ComputableTidilyInPolyTime (fun a => (programField (ws a) (pc a) (field a)).length) e encUnary :=
length_bits.comp (programField_poly hw hp hf)
theorem programArgBit_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)} {pc field bit : A → ℕ}
(hw : ComputableTidilyInPolyTime ws e (encList encBits))
(hp : ComputableTidilyInPolyTime pc e encUnary)
(hf : ComputableTidilyInPolyTime field e encUnary)
(hb : ComputableTidilyInPolyTime bit e encUnary) :
ComputableTidilyInPolyTime (fun a =>
(ofBits (programField (ws a) (pc a) (field a))).testBit (bit a)) e encBool :=
binary_testBit (program_arg_poly hw hp hf) hb
/-- Static operands have unbounded numerical value. Returning unary is safe only
after capping at an independently polynomially bounded positive parameter. -/
theorem programArgCapped_poly {A : Type} {e : A ↪ List Bool}
{ws : A → List (List Bool)} {pc field cap : A → ℕ}
(hw : ComputableTidilyInPolyTime ws e (encList encBits))
(hp : ComputableTidilyInPolyTime pc e encUnary)
(hf : ComputableTidilyInPolyTime field e encUnary)
(hc : ComputableTidilyInPolyTime cap e encUnary) :
ComputableTidilyInPolyTime (fun a =>
min (cap a) (ofBits (programField (ws a) (pc a) (field a)))) e encUnary :=
(ComputableInPolyTime.binary_min_unary' hc.computableInPolyTime
(program_arg_poly hw hp hf).computableInPolyTime).tidy
end CNFEncComplexity.Robson
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
structure BinaryPort where
width : ℕ
bit : ℕ → ℕ
def BinaryPort.value (a : Assignment) (w : BinaryPort) : ℕ := wireValue a w.bit w.width
def BinaryPort.equalGates (z : ℕ) (x y : BinaryPort) : List Gate :=
paddedWordCopy (max x.width y.width) x.width y.width z x.bit y.bit
theorem BinaryPort.equalGates_exact (z : ℕ) (x y : BinaryPort) (a : Assignment) (hz : a z=false) :
(∀ g ∈ x.equalGates z y,g.Holds a) ↔ x.value a = y.value a :=
paddedWordCopy_exact _ _ _ z x.bit y.bit a (Nat.le_max_left _ _) (Nat.le_max_right _ _) hz
def BinaryPort.nonzeroGates (w : BinaryPort) : List Gate :=
[.assert ((List.range w.width).map (fun i => .Pos (w.bit i)))]
theorem BinaryPort.nonzeroGates_exact (w : BinaryPort) (a : Assignment) :
(∀ g ∈ w.nonzeroGates,g.Holds a) ↔ w.value a ≠ 0 := by
have hZero : w.value a = 0 ↔ ∀ i < w.width, a (w.bit i)=false := by
unfold BinaryPort.value
rw [← wordConst_exact w.width w.bit 0 (Nat.pow_pos (by decide)) a]
simp [wordConst,Gate.Holds]
simp only [BinaryPort.nonzeroGates,List.forall_mem_singleton,Gate.Holds,satisfiesClause_iff]
constructor
· rintro ⟨lit,hlit,hs⟩ he
obtain ⟨i,hi,rfl⟩ := List.mem_map.mp hlit
change a (w.bit i)=true at hs
rw [(hZero.mp he) i (List.mem_range.mp hi)] at hs
contradiction
· intro hn
classical
have hE : ∃ i < w.width, a (w.bit i)=true := by
by_contra! ha
exact hn (hZero.mpr (fun i hi => Bool.eq_false_iff.mpr (ha i hi)))
obtain ⟨i,hi,hs⟩ := hE
exact ⟨.Pos (w.bit i),List.mem_map.mpr ⟨i,List.mem_range.mpr hi,rfl⟩,hs⟩
def accessPatternGates (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(i : ℕ) (p : PacketAccessPattern) : List Gate :=
.pin (slotRowWrite n t s i) p.writes ::
(BinaryPort.mk (2^s.2) (slotRowAddress n t s i)).equalGates z (words p.address) ++
(BinaryPort.mk (2^s.2) (slotRowValue n t s i)).equalGates z (words p.value)
theorem accessPatternGates_exact (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(i : ℕ) (p : PacketAccessPattern) (a : Assignment) (packet : Packet)
(hz : a z=false) (ha : (words p.address).value a = p.address.eval packet)
(hv : (words p.value).value a = p.value.eval packet) :
(∀ g ∈ accessPatternGates n t z s words i p,g.Holds a) ↔
slotRawAction a n t s i = p.eval packet := by
rw [accessPatternGates,List.forall_mem_append,List.forall_mem_cons,
BinaryPort.equalGates_exact _ _ _ _ hz,BinaryPort.equalGates_exact _ _ _ _ hz,
ha,hv,and_assoc]
simp only [Gate.Holds]
change
(a (slotRowWrite n t s i) = p.writes ∧
wireValue a (slotRowAddress n t s i) (2^s.2) = p.address.eval packet ∧
wireValue a (slotRowValue n t s i) (2^s.2) = p.value.eval packet) ↔ _
simp only [slotRawAction,PacketAccessPattern.eval,MemoryAccess.mk.injEq]
tauto
/-- A presence mask fixes the order of used physical lanes. A branch with a
different expected lane count is impossible. -/
def accessListGates (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort) :
List ℕ → List PacketAccessPattern → List Gate
| [],[] => []
| i::is,p::ps => accessPatternGates n t z s words i p ++ accessListGates n t z s words is ps
| _,_ => [.assert []]
theorem accessListGates_exact (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(is : List ℕ) (ps : List PacketAccessPattern) (a : Assignment) (packet : Packet)
(hz : a z=false) (hw : ∀ p ∈ ps, (words p.address).value a = p.address.eval packet ∧
(words p.value).value a = p.value.eval packet) :
(∀ g ∈ accessListGates n t z s words is ps,g.Holds a) ↔
is.map (slotRawAction a n t s) = ps.map (PacketAccessPattern.eval packet) := by
induction is generalizing ps with
| nil =>
cases ps <;> simp [accessListGates,Gate.Holds,satisfiesClause]
| cons i is ih =>
cases ps with
| nil => simp [accessListGates,Gate.Holds,satisfiesClause]
| cons p ps =>
have hd := hw p List.mem_cons_self
rw [accessListGates,List.forall_mem_append,
accessPatternGates_exact _ _ _ _ _ _ _ _ _ hz hd.1 hd.2,
ih ps (fun q hq => hw q (List.mem_cons_of_mem _ hq))]
simp
def slotPacket (a : Assignment) (n t : ℕ) (s : ℕ × ℕ) (cost : ℕ) : Packet :=
let p := slotView a n t s
⟨p.1,p.2,cost⟩
def packetFormatGates (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(m : PacketPattern) (mask : ℕ) : List Gate :=
slotPacketShape n t s m.readsInput mask ++
accessListGates n t z s words (maskLanes mask) m.accesses ++
(match m.zero with
| none => []
| some true => boundedWordConst (words (.operand 0)).width (words (.operand 0)).bit 0
| some false => (words (.operand 0)).nonzeroGates)
theorem packetFormatGates_sound (n t z : ℕ) (s : ℕ × ℕ)
(words : PacketExpr → BinaryPort) (m : PacketPattern) (mask : ℕ) (a : Assignment) (cost : ℕ)
(hz : a z=false)
(hw : ∀ p ∈ m.accesses,
(words p.address).value a = p.address.eval (slotPacket a n t s cost) ∧
(words p.value).value a = p.value.eval (slotPacket a n t s cost))
(hOp : (words (.operand 0)).value a = (slotPacket a n t s cost).operand 0)
(h : ∀ g ∈ packetFormatGates n t z s words m mask,g.Holds a) :
let p := slotPacket a n t s cost
p.input = (if m.readsInput then some (PacketExpr.eval p .symbol) else none) ∧
p.accesses = m.accesses.map (PacketAccessPattern.eval p) ∧
∀ flag, m.zero=some flag → (p.operand 0=0 ↔ flag=true) := by
rw [packetFormatGates,List.forall_mem_append,List.forall_mem_append] at h
obtain ⟨⟨hShape,hAccess⟩,hZero⟩ := h
have hV := slotPacketShape_view a n t s m.readsInput mask hShape
have hInput := congrArg Prod.fst hV
have hRows := congrArg Prod.snd hV
have hAs := (accessListGates_exact n t z s words _ _ a (slotPacket a n t s cost) hz hw).mp hAccess
refine ⟨?_,hRows.trans hAs,?_⟩
· change (slotView a n t s).1 = _
cases h : m.readsInput <;> simp [h,PacketExpr.eval,slotPacket,hInput]
· intro flag hFlag
rw [hFlag] at hZero
cases flag
· rw [BinaryPort.nonzeroGates_exact,hOp] at hZero
simpa using hZero
· rw [boundedWordConst_exact] at hZero
change (words (.operand 0)).value a = 0 at hZero
rw [hOp] at hZero
simp [hZero]
theorem packetFormatGates_complete (n t z : ℕ) (s : ℕ × ℕ)
(words : PacketExpr → BinaryPort) (m : PacketPattern) (a : Assignment) (cost : ℕ)
(hz : a z=false)
(hw : ∀ p ∈ m.accesses,
(words p.address).value a = p.address.eval (slotPacket a n t s cost) ∧
(words p.value).value a = p.value.eval (slotPacket a n t s cost))
(hOp : (words (.operand 0)).value a = (slotPacket a n t s cost).operand 0)
(h : let p := slotPacket a n t s cost
p.input = (if m.readsInput then some (PacketExpr.eval p .symbol) else none) ∧
p.accesses = m.accesses.map (PacketAccessPattern.eval p) ∧
∀ flag, m.zero=some flag → (p.operand 0=0 ↔ flag=true)) :
∃ mask < 8, ∀ g ∈ packetFormatGates n t z s words m mask,g.Holds a := by
let p := slotPacket a n t s cost
change p.input = _ ∧ p.accesses = _ ∧ _ at h
obtain ⟨mask,hM,hFlags⟩ := mask_exists (fun i => a (slotRowPresent n t s i))
have hIn : a (port n t s 0 0) = m.readsInput := by
have hP := h.1
change portInput a n t s = _ at hP
cases hA : a (port n t s 0 0) <;> cases hR : m.readsInput <;>
simp_all [portInput]
have hShape := (slotPacketShape_exact a n t s m.readsInput mask).mpr ⟨hIn,hFlags⟩
have hRows := congrArg Prod.snd (slotPacketShape_view a n t s m.readsInput mask hShape)
have hAccess := (accessListGates_exact n t z s words (maskLanes mask) m.accesses a p hz hw).mpr
(hRows.symm.trans h.2.1)
refine ⟨mask,hM,?_⟩
rw [packetFormatGates,List.forall_mem_append,List.forall_mem_append]
refine ⟨⟨hShape,hAccess⟩,?_⟩
change (words (.operand 0)).value a = p.operand 0 at hOp
cases hZero : m.zero with
| none => simp
| some flag =>
cases flag
· rw [BinaryPort.nonzeroGates_exact,hOp]
simpa using h.2.2 false hZero
· rw [boundedWordConst_exact]
change (words (.operand 0)).value a = 0
rw [hOp]
exact (h.2.2 true hZero).mpr rfl
theorem accessPatternGates_length (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(i : ℕ) (p : PacketAccessPattern) (w : ℕ)
(hs : 2^s.2 ≤ w) (ha : (words p.address).width ≤ w) (hv : (words p.value).width ≤ w) :
(accessPatternGates n t z s words i p).length ≤ 1+2*w := by
have h1 := max_le hs ha
have h2 := max_le hs hv
simp only [accessPatternGates,List.length_append,List.length_cons,
BinaryPort.equalGates,paddedWordCopy,length_wordCopy]
omega
theorem accessListGates_length (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(is : List ℕ) (ps : List PacketAccessPattern) (w : ℕ) (hs : 2^s.2 ≤ w)
(hFit : ∀ p ∈ ps, (words p.address).width ≤ w ∧ (words p.value).width ≤ w) :
(accessListGates n t z s words is ps).length ≤ 1+is.length*(1+2*w) := by
induction is generalizing ps with
| nil =>
cases ps <;> simp [accessListGates]
| cons i is ih =>
cases ps with
| nil => simp [accessListGates]
| cons p ps =>
obtain ⟨ha,hv⟩ := hFit p List.mem_cons_self
have h1 := accessPatternGates_length n t z s words i p w hs ha hv
have h2 := ih ps (fun q hq => hFit q (List.mem_cons_of_mem _ hq))
simp only [accessListGates,List.length_append,List.length_cons,Nat.add_mul,Nat.one_mul]
omega
theorem packetFormatGates_length (n t z : ℕ) (s : ℕ × ℕ) (words : PacketExpr → BinaryPort)
(m : PacketPattern) (mask w : ℕ) (hs : 2^s.2 ≤ w)
(hFit : ∀ p ∈ m.accesses, (words p.address).width ≤ w ∧ (words p.value).width ≤ w)
(h0 : (words (.operand 0)).width ≤ w) :
(packetFormatGates n t z s words m mask).length ≤ 9+7*w := by
have hShape : (slotPacketShape n t s m.readsInput mask).length = 4 := by
simp [slotPacketShape]
have hML : (maskLanes mask).length ≤ 3 := by
simpa [maskLanes] using List.length_filter_le (p := physicalMask mask) (List.range 3)
have hData := accessListGates_length n t z s words (maskLanes mask) m.accesses w hs hFit
have hMono := Nat.mul_le_mul_right (1+2*w) hML
have hConst := boundedWordConst_length (words (.operand 0)).width (words (.operand 0)).bit 0
simp only [packetFormatGates,List.length_append,hShape]
cases h : m.zero with
| none => simp [h] <;> omega
| some b =>
cases b <;> simp [h,BinaryPort.nonzeroGates] <;> omega
end CNFEncComplexity.Robson
/- robson-gate-rename -/
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime
def renameLiteralCode (name : ℕ → ℕ) (r : ℕ) : ℕ := 2*name (r/2)+r%2
theorem renameLiteralCode_exact (name : ℕ → ℕ) (l : Literal) :
renameLiteralCode name (literalN l) = literalN (Literal.rename name l) := by
cases l with
| Neg r => simp [renameLiteralCode,literalN,Literal.rename,show (2*r)/2=r by omega,show (2*r)%2=0 by omega]
| Pos r => simp [renameLiteralCode,literalN,Literal.rename,show (2*r+1)/2=r by omega,show (2*r+1)%2=1 by omega]
def renamedCode (name : ℕ → ℕ) (r : List ℕ) : List ℕ :=
let tag := r.headD 0
tag :: (if tag = 8 then r.tail.map (renameLiteralCode name) else r.tail.map name)
theorem renamedCode_exact (name : ℕ → ℕ) (g : Gate) :
(g.rename name).code = renamedCode name g.code := by
cases g with
| pin o b => cases b <;> rfl
| copy | inv | conj | disj | parity | mux => rfl
| assert c =>
simp only [Gate.rename,Gate.code,renamedCode,List.headD_cons,if_pos rfl,List.tail_cons,
clauseN,List.map_map,List.cons.injEq,true_and]
apply List.map_congr_left
intro lit _
exact (renameLiteralCode_exact name lit).symm
private theorem gateCode_poly : ComputableTidilyInPolyTime Gate.code gateEnc (encList encUnary) :=
(id' (encIn:=gateEnc)).of_enc_eq fun _ => rfl
theorem gateRename_poly {A : Type} {e : A ↪ List Bool} {name : A → ℕ → ℕ}
(hName : ComputableTidilyInPolyTime (fun p : A×ℕ => name p.1 p.2)
(encPair e encUnary) encUnary) :
ComputableTidilyInPolyTime (fun p : A×Gate => p.2.rename (name p.1))
(encPair e gateEnc) gateEnc := by
let ep := encPair e gateEnc
let ei := encPair ep encUnary
have hA := fst e gateEnc
have hGate := snd e gateEnc
have hCode := gateCode_poly.comp hGate
have hTag := (headD (encA:=encUnary) 0).comp hCode
have hTail := (listTail encUnary).comp hCode
have hPref := fst ep encUnary
have hIdx := snd ep encUnary
have hN := hName.comp ((hA.comp hPref).prod hIdx)
have hDiv : ComputableTidilyInPolyTime (fun p : (A×Gate)×ℕ => p.2 / 2) ei encUnary :=
unary_div_poly.comp (hIdx.prod (const 2))
have hMod : ComputableTidilyInPolyTime (fun p : (A×Gate)×ℕ => p.2 % 2) ei encUnary :=
unary_mod_poly.comp (hIdx.prod (const 2))
have hNL := hName.comp ((hA.comp hPref).prod hDiv)
have hLiteral := unary_add.comp ((unary_mul.comp ((const 2).prod hNL)).prod hMod)
have hTailN := mapWithInput (f:=fun (p : A×Gate) k => name p.1 k) hTail hN
have hTailL := mapWithInput (f:=fun (p : A×Gate) k => renameLiteralCode (name p.1) k) hTail hLiteral
have hPred := unary_beq hTag (const 8)
apply gate_of_fields (code:=fun p : A×Gate => renamedCode (name p.1) p.2.code)
· have hh := cons' hTag (hPred.ite' hTailL hTailN)
convert hh using 1
funext p
simp [renamedCode,Function.comp_def,beq_iff_eq]
· intro p
exact renamedCode_exact _ _
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
/-- Keep shared names and inject private names into the chosen residue class. -/
def componentWire (S : ℕ) (part : Fin 3) (r : ℕ) : ℕ :=
if r < S then r else S+3*(r-S)+part.val
theorem componentWire_owns (S : ℕ) (part : Fin 3) (r : ℕ) : owns S part (componentWire S part r) := by
by_cases h : r < S
· exact .inl (by simpa [componentWire,h] using h)
· right
simp [componentWire,h,Nat.add_assoc,Nat.add_mod,Nat.mod_eq_of_lt part.isLt]
def componentUnwire (S : ℕ) (r : ℕ) : ℕ :=
if r < S then r else S+(r-S)/3
theorem componentUnwire_wire (S : ℕ) (part : Fin 3) (r : ℕ) :
componentUnwire S (componentWire S part r) = r := by
by_cases h : r < S
· simp [componentWire,componentUnwire,h]
· have hh : ¬ S+3*(r-S)+part.val < S := by omega
have hs : (S+3*(r-S)+part.val)-S=3*(r-S)+part.val := by omega
have hp : part.val/3=0 := Nat.div_eq_of_lt part.isLt
rw [componentWire,if_neg h,componentUnwire,if_neg hh,hs,Nat.mul_add_div (by decide),hp]
omega
theorem componentRename_extends (S : ℕ) (part : Fin 3) (gates : List Gate) (a : Assignment) :
ExtendsWith S (gates.map (Gate.rename (componentWire S part))) a ↔ ExtendsWith S gates a := by
constructor
· rintro ⟨b,hKeep,hG⟩
refine ⟨b∘componentWire S part,fun r hr => ?_,(renamedCircuit_correct _ _ _).1 hG⟩
simpa [Function.comp_def,componentWire,hr] using hKeep r hr
· rintro ⟨b,hKeep,hG⟩
refine ⟨b∘componentUnwire S,fun r hr => ?_,(renamedCircuit_correct _ _ _).2 ?_⟩
· simpa [Function.comp_def,componentUnwire,hr] using hKeep r hr
· simpa [Function.comp_def,componentUnwire_wire] using hG
theorem componentRename_owns (S : ℕ) (part : Fin 3) (gs : List Gate)
(g : Gate) (hg : g ∈ gs.map (Gate.rename (componentWire S part))) (r : ℕ)
(hr : r ∈ CNFEncComplexity.Robson.Gate.names g) : owns S part r := by
obtain ⟨g',_,rfl⟩ := List.mem_map.mp hg
change r ∈ RobsonCNF.Gate.names (g'.rename (componentWire S part)) at hr
rw [renamedNames] at hr
obtain ⟨r',_,rfl⟩ := List.mem_map.mp hr
exact componentWire_owns _ _ _
theorem componentRename_poly {A : Type} {e : A ↪ List Bool} (part : Fin 3)
{S : A → ℕ} {gs : A → List Gate} (hS : ComputableTidilyInPolyTime S e encUnary)
(hgs : ComputableTidilyInPolyTime gs e (encList gateEnc)) :
ComputableTidilyInPolyTime (fun a => (gs a).map (Gate.rename (componentWire (S a) part)))
e (encList gateEnc) := by
have hPrefix := fst e encUnary
have hBase := hS.comp hPrefix
have hr := snd e encUnary
have hCond := unary_lt' hr hBase
have hRest := unary_sub.comp (hr.prod hBase)
have hNum := unary_mul.comp ((const 3).prod hRest)
have hEnd := unary_add.comp ((unary_add.comp (hBase.prod hNum)).prod (const part.val))
have hName : ComputableTidilyInPolyTime
(fun p : A×ℕ => componentWire (S p.1) part p.2) (encPair e encUnary) encUnary := by
simpa only [componentWire,decide_eq_true_eq,Function.comp_def] using hCond.ite' hr hEnd
exact mapWithInput hgs (gateRename_poly (e := e) (name := fun a => componentWire (S a) part) hName)
end CNFEncComplexity.Robson
/- shared port name bounds -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
theorem sharedLimit_poly {A : Type} {e : A ↪ List Bool} {n t : A → ℕ}
(hn : ComputableTidilyInPolyTime n e encUnary) (ht : ComputableTidilyInPolyTime t e encUnary) :
ComputableTidilyInPolyTime (fun a => sharedLimit (n a) (t a)) e encUnary := by
have hH := layoutHeight_poly.comp ht
have hW := layoutHorizon_poly.comp ht
have hA := unary_add.comp (hH.prod (const 1))
have hB := unary_mul.comp (hW.prod hA)
have hC := unary_mul.comp (hB.prod (const 19))
have hD := unary_mul.comp (hC.prod hW)
exact unary_add.comp (hn.prod hD)
end CNFEncComplexity.Robson
/- formula compiler -/
/- robson-trace-kernel -/
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM
open Turing.MultiTapeTM.ComputableTidilyInPolyTime
/-- Intermediate formula syntax with literals represented in unary, matching the
encoding used to feed formulas to the SAT language. -/
def unaryFormulaEnc : Formula ↪ List Bool :=
(⟨formulaN,formulaN_injective⟩ : Formula ↪ List (List Nat)).trans
(encList (encList encUnary))
def cookFormulaEnc : Formula ↪ List Bool :=
⟨encodeFormula,encodeFormula_injective⟩
private theorem formatNat_eq (n : ℕ) : CookLevin.encodeNat n = List.replicate n true ++ [false] := by
induction n with
| zero => rfl
| succ n ih =>
rw [CookLevin.encodeNat,List.replicate_succ,ih,List.cons_append]
private theorem formatNat :
ComputableTidilyInPolyTime (fun n => true :: CookLevin.encodeNat n) encUnary encBits := by
have h := bitsCons (const true) (bitsAppend (bitsReplicate true) (const [false]))
simpa only [formatNat_eq] using h
private theorem formatList :
ComputableTidilyInPolyTime (fun l => true :: CookLevin.encodeListNat l)
(encList encUnary) encBits := by
have hb := bitsFlatten ((map formatNat).comp (id' (encIn := encList encUnary)))
have he (l : List ℕ) :
CookLevin.encodeListNat l = (l.map fun n => true :: CookLevin.encodeNat n).flatten ++ [false] := by
simpa only [List.map_id, List.flatten_eq_flatMap, List.flatMap_map, id_eq] using
CookLevin.encodeListNat_map id l
have h := bitsCons (const true) (bitsAppend hb (const [false]))
simpa only [he,Function.comp_apply,id_eq] using h
/-- Serialize explicit unary literal lists into Cook–Levin's exact bit format. -/
theorem encodeFormulaN_polytime :
ComputableTidilyInPolyTime CookLevin.encodeFormulaN (encList (encList encUnary)) encBits := by
have hb := bitsFlatten ((map formatList).comp (id' (encIn := encList (encList encUnary))))
have he (l : List (List ℕ)) :
CookLevin.encodeFormulaN l = (l.map fun w => true :: CookLevin.encodeListNat w).flatten ++ [false] := by
simpa only [List.map_id, List.flatten_eq_flatMap, List.flatMap_map, id_eq] using
CookLevin.encodeFormulaN_map id l
have h := bitsAppend hb (const [false])
have he' : CookLevin.encodeFormulaN = (fun l => (l.map fun w =>
true :: CookLevin.encodeListNat w).flatten ++ [false]) := funext he
rw [he']
exact h
/-- Transfer a verified formula constructor on explicit unary literals to the
required Cook–Levin formula encoding without a change to its mathematical output. -/
theorem to_cookFormulaEnc {α : Type} {encIn : α ↪ List Bool} {build : α → Formula}
(h : ComputableInPolyTime build encIn unaryFormulaEnc) :
ComputableInPolyTime build encIn cookFormulaEnc := by
have hlist : ComputableTidilyInPolyTime (fun x => formulaN (build x)) encIn
(encList (encList encUnary)) := h.tidy.of_enc_eq (fun x => rfl)
exact ((encodeFormulaN_polytime.comp hlist).of_enc_eq (fun x => rfl)).computableInPolyTime
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM
open Turing.MultiTapeTM.ComputableTidilyInPolyTime
/-- The constructor tag precedes its wire numbers. A raw assertion stores its
literal numbers directly after the tag. -/
private abbrev Recipe := List (List (ℕ × ℕ))
private abbrev encFields := encList encUnary
private abbrev encFormulaFields := encList encFields
private abbrev encLiteralRecipe := encPair encUnary encUnary
private abbrev encClauseRecipe := encList encLiteralRecipe
private abbrev encRecipe := encList encClauseRecipe
/-- Each recipe literal specifies its index in the constructor record and its sign. -/
private def recipes : List Recipe := [
[[(1,0)]],
[[(1,1)]],
[[(1,0),(2,1)],[(1,1),(2,0)]],
[[(1,0),(2,0)],[(1,1),(2,1)]],
[[(1,0),(2,1)],[(1,0),(3,1)],[(1,1),(2,0),(3,0)]],
[[(1,1),(2,0)],[(1,1),(3,0)],[(1,0),(2,1),(3,1)]],
[[(1,1),(2,0),(3,1)],[(1,1),(2,1),(3,0)],[(1,0),(2,1),(3,1)],[(1,0),(2,0),(3,0)]],
[[(2,0),(1,0),(3,1)],[(2,0),(1,1),(3,0)],[(2,1),(1,0),(4,1)],[(2,1),(1,1),(4,0)]]
]
private def lookup (l : List ℕ) (i : ℕ) : ℕ :=
(l[i]?).getD 0
private def buildLiteral (l : List ℕ) (spec : ℕ × ℕ) : ℕ :=
2*lookup l spec.1+spec.2
private def buildClause (l : List ℕ) (spec : List (ℕ × ℕ)) : List ℕ :=
spec.map (buildLiteral l)
private def buildClauses (l : List ℕ) : List (List ℕ) :=
if lookup l 0 < 8 then
((recipes[lookup l 0]?).getD []).map (buildClause l)
else [l.drop 1]
private theorem buildClauses_exact (g : Gate) :
buildClauses g.code = formulaN g.compile := by
cases g with
| pin out b => cases b <;> rfl
| copy => rfl
| inv => rfl
| conj => rfl
| disj => rfl
| parity => rfl
| mux => rfl
| assert => rfl
private theorem lookup_poly {α : Type} {input : α ↪ List Bool} {l : α → List ℕ} {i : α → ℕ}
(hl : ComputableTidilyInPolyTime l input encFields)
(hi : ComputableTidilyInPolyTime i input encUnary) :
ComputableTidilyInPolyTime (fun x => lookup (l x) (i x)) input encUnary :=
(optionGetD encUnary).comp ((ComputableTidilyInPolyTime.getElem? hl hi).prod (const 0))
private theorem buildLiteral_poly : ComputableTidilyInPolyTime
(fun p : List ℕ × (ℕ × ℕ) => buildLiteral p.1 p.2)
(encPair encFields encLiteralRecipe) encUnary := by
have hl := fst encFields encLiteralRecipe
have hs := snd encFields encLiteralRecipe
have hlook := lookup_poly hl hs.fst'
exact unary_add.comp ((unary_mul.comp ((const 2).prod hlook)).prod hs.snd')
private theorem buildClause_poly : ComputableTidilyInPolyTime
(fun p : List ℕ × List (ℕ × ℕ) => buildClause p.1 p.2)
(encPair encFields encClauseRecipe) encFields :=
mapWith buildLiteral_poly (fst _ _) (snd _ _)
private theorem recipe_poly : ComputableTidilyInPolyTime
(fun l : List ℕ => (recipes[lookup l 0]?).getD [])
encFields encRecipe :=
(optionGetD encRecipe).comp
((ComputableTidilyInPolyTime.getElem? (encL := encList encRecipe) (const recipes) (lookup_poly (id' (encIn := encFields)) (const 0))).prod
(const []))
private theorem buildClauses_poly : ComputableTidilyInPolyTime buildClauses encFields encFormulaFields := by
have hi := id' (encIn := encFields)
have htag := lookup_poly hi (const 0)
have hbranch := unary_lt' htag (const 8)
have hy := mapWith buildClause_poly hi recipe_poly
have hn := cons' (listDropWithInput hi (const 1)) (const [])
convert hbranch.ite' hy hn using 1
funext x
simp [buildClauses]
theorem compile_polytime :
ComputableInPolyTime compile (encList gateEnc) unaryFormulaEnc := by
have hcode : ComputableTidilyInPolyTime Gate.code gateEnc encFields :=
ComputableTidilyInPolyTime.of_eq (fun _ => rfl)
have hGate : ComputableTidilyInPolyTime (fun g : Gate => buildClauses g.code)
gateEnc encFormulaFields := buildClauses_poly.comp hcode
have hPair : ComputableTidilyInPolyTime (fun p : List Gate × Gate => buildClauses p.2.code)
(encPair (encList gateEnc) gateEnc) encFormulaFields := hGate.comp (snd _ _)
have hs := flatMapWithInput (f := fun (_ : List Gate) (g : Gate) => buildClauses g.code)
(id' (encIn := encList gateEnc)) hPair
apply ComputableTidilyInPolyTime.computableInPolyTime
refine hs.of_enc_eq (fun gs => ?_)
change encFormulaFields (formulaN (compile gs)) = encFormulaFields (gs.flatMap (buildClauses ∘ Gate.code))
congr 1
simp [compile, formulaN, List.map_flatMap, buildClauses_exact, Function.comp_def]
end CNFEncComplexity.RobsonCNF
/- literal encoding -/
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM ComputableTidilyInPolyTime
variable {A : Type} {input : A ↪ List Bool}
theorem negative_poly {x : A → ℕ} (hx : ComputableTidilyInPolyTime x input encUnary) :
ComputableTidilyInPolyTime (fun a => literalN (.Neg (x a))) input encUnary :=
unary_mul.comp ((const 2).prod hx)
theorem positive_poly {x : A → ℕ} (hx : ComputableTidilyInPolyTime x input encUnary) :
ComputableTidilyInPolyTime (fun a => literalN (.Pos (x a))) input encUnary :=
unary_add.comp ((negative_poly hx).prod (const 1))
theorem assert2_poly {x y : A → Literal}
(hx : ComputableTidilyInPolyTime (fun a => literalN (x a)) input encUnary)
(hy : ComputableTidilyInPolyTime (fun a => literalN (y a)) input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.assert [x a,y a]) input gateEnc :=
gate_assert (cons' hx (cons' hy (const [])))
theorem assert3_poly {x y z : A → Literal}
(hx : ComputableTidilyInPolyTime (fun a => literalN (x a)) input encUnary)
(hy : ComputableTidilyInPolyTime (fun a => literalN (y a)) input encUnary)
(hz : ComputableTidilyInPolyTime (fun a => literalN (z a)) input encUnary) :
ComputableTidilyInPolyTime (fun a => Gate.assert [x a,y a,z a]) input gateEnc :=
gate_assert (cons' hx (cons' hy (cons' hz (const []))))
end CNFEncComplexity.RobsonCNF
/- framed binary ports -/
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF
def BinaryPort.Below (w : BinaryPort) (limit : ℕ) : Prop :=
∀ i < w.width, w.bit i < limit
def BinaryPort.InFrame (w : BinaryPort) (common lo hi : ℕ) : Prop :=
∀ i < w.width, w.bit i < common ∨ lo ≤ w.bit i ∧ w.bit i < hi
def GateFrame (gs : List Gate) (common lo hi : ℕ) : Prop :=
∀ g ∈ gs, ∀ r ∈ g.names, r < common ∨ lo ≤ r ∧ r < hi
def GateSat (a : Assignment) (gs : List Gate) : Prop :=
∀ g ∈ gs, g.Holds a
def Keeps (a b : Assignment) (lo hi : ℕ) : Prop :=
∀ k, k < lo ∨ hi ≤ k → b k = a k
theorem BinaryPort.value_congr (w : BinaryPort) (a b : Assignment)
(h : ∀ i < w.width, a (w.bit i) = b (w.bit i)) : w.value a = w.value b :=
wireValue_congr h
theorem GateSat.append {a : Assignment} {g h : List Gate} :
GateSat a (g++h) ↔ GateSat a g ∧ GateSat a h :=
List.forall_mem_append
theorem GateFrame.append {g h : List Gate} {common lo hi : ℕ} :
GateFrame (g++h) common lo hi ↔ GateFrame g common lo hi ∧ GateFrame h common lo hi := by
exact List.forall_mem_append
theorem GateFrame.mono {g : List Gate} {p lo hi p' lo' hi' : ℕ}
(h : GateFrame g p lo hi) (hp : p ≤ p') (hl : lo' ≤ lo) (hh : hi ≤ hi') :
GateFrame g p' lo' hi' := by
intro b hb i hi'
rcases h b hb i hi' with h | ⟨h1,h2⟩
· exact .inl (h.trans_le hp)
· exact .inr ⟨hl.trans h1,h2.trans_le hh⟩
theorem BinaryPort.InFrame.mono {w : BinaryPort} {p lo hi p' lo' hi' : ℕ}
(h : w.InFrame p lo hi) (hp : p ≤ p') (hl : lo' ≤ lo) (hh : hi ≤ hi') :
w.InFrame p' lo' hi' := by
intro i hi'
rcases h i hi' with h | ⟨h1,h2⟩
· exact .inl (h.trans_le hp)
· exact .inr ⟨hl.trans h1,h2.trans_le hh⟩
theorem BinaryPort.InFrame.below {w : BinaryPort} {p lo hi : ℕ}
(h : w.InFrame p lo hi) (hp : p ≤ hi) : w.Below hi := by
intro i hi'
rcases h i hi' with h | ⟨_,h⟩
· exact h.trans_le hp
· exact h
theorem GateSat.congr_framed {a b : Assignment} {gs : List Gate} {common lo hi : ℕ}
(h : GateSat a gs) (hf : GateFrame gs common lo hi)
(he : ∀ i, i < common ∨ lo ≤ i ∧ i < hi → a i = b i) : GateSat b gs := by
intro g hg
exact (g.holds_congr a b (fun i hi => he i (hf g hg i hi))).mp (h g hg)
theorem Keeps.trans {a b c : Assignment} {l u v : ℕ} (h : Keeps a b l u)
(h' : Keeps b c u v) (hl : l ≤ u) (hu : u ≤ v) : Keeps a c l v := by
intro i hi
have hi₁ : i < l ∨ u ≤ i := by omega
have hi₂ : i < u ∨ v ≤ i := by omega
rw [h' i hi₂,h i hi₁]
def constantPort (z o n c : ℕ) : BinaryPort :=
⟨n, fun i => if c.testBit i then o else z⟩
theorem constantPort_value {a : Assignment} {z o n c : ℕ}
(hz : a z = false) (ho : a o = true) (hc : c < 2^n) :
(constantPort z o n c).value a = c := by
unfold BinaryPort.value
rw [wireValue_eq_bitString]
have hh : (fun i : Fin n => a ((constantPort z o n c).bit i.val)) =
(Cslib.BitString.equivFin n).symm ⟨c,hc⟩ := by
funext i
rw [Cslib.BitString.equivFin_symm_apply]
simp only [constantPort]
cases h : c.testBit i.val <;> simp [h,hz,ho]
change ((Cslib.BitString.equivFin n) (fun i => a ((constantPort z o n c).bit i.val))).val = c
rw [hh,Equiv.apply_symm_apply]
theorem constantPort_frame {z o n c p lo hi : ℕ} (hz : z < p) (ho : o < p) :
(constantPort z o n c).InFrame p lo hi := by
intro i _
have h : (if c.testBit i then o else z) < p := by split <;> assumption
exact .inl h
def cappedPort (z o n c : ℕ) : BinaryPort :=
constantPort z o (n+1) (min c (2^n))
theorem cappedPort_value {a : Assignment} {z o n c : ℕ}
(hz : a z = false) (ho : a o = true) :
(cappedPort z o n c).value a = min c (2^n) := by
apply constantPort_value hz ho
exact (min_le_right _ _).trans_lt (Nat.pow_lt_pow_right (by decide) (Nat.lt_succ_self _))
def BinaryPort.padded (w : BinaryPort) (z n : ℕ) : BinaryPort :=
⟨n,paddedKey w.width z w.bit⟩
theorem BinaryPort.padded_value (w : BinaryPort) {a : Assignment} {z n : ℕ}
(hz : a z=false) (hn : w.width ≤ n) :
(w.padded z n).value a = w.value a :=
wireValue_pad a _ _ _ hz _ hn
theorem BinaryPort.padded_frame {w : BinaryPort} {z n common lo hi : ℕ}
(h : w.InFrame common lo hi) (hz : z < common) :
(w.padded z n).InFrame common lo hi := by
intro i _
change (if i < w.width then w.bit i else z) < common ∨
lo ≤ (if i < w.width then w.bit i else z) ∧ (if i < w.width then w.bit i else z) < hi
split
· exact h _ (by assumption)
· exact .inl hz
def BinaryPort.addWidth (x y : BinaryPort) : ℕ := max x.width y.width
def BinaryPort.addPort (b : ℕ) (x y : BinaryPort) : BinaryPort :=
⟨x.addWidth y+1,addOutputWire b (x.addWidth y)⟩
def BinaryPort.addGates (z b : ℕ) (x y : BinaryPort) : List Gate :=
let k := x.addWidth y
rippleCircuit false b k (x.padded z k).bit (y.padded z k).bit
def BinaryPort.addEnd (b : ℕ) (x y : BinaryPort) : ℕ := b+8*x.addWidth y+1
theorem BinaryPort.addPort_names (b : ℕ) (x y : BinaryPort) {i : ℕ}
(hi : i < (x.addPort b y).width) :
b ≤ (x.addPort b y).bit i ∧ (x.addPort b y).bit i < x.addEnd b y := by
simp only [BinaryPort.addPort,BinaryPort.addEnd,addOutputWire,rippleCarryWire,rippleBitWire] at hi ⊢
split <;> omega
theorem BinaryPort.addGates_exact (z b : ℕ) (x y : BinaryPort) (a : Assignment)
(hz : a z=false) (h : GateSat a (x.addGates z b y)) :
(x.addPort b y).value a = x.value a+y.value a := by
have q := rippleCircuit_add_exact b (x.addWidth y) (x.padded z _).bit (y.padded z _).bit a h
change (x.addPort b y).value a = (x.padded z (x.addWidth y)).value a +
(y.padded z (x.addWidth y)).value a at q
rw [x.padded_value hz (show x.width ≤ x.addWidth y from le_max_left ..),
y.padded_value hz (show y.width ≤ x.addWidth y from le_max_right ..)] at q
exact q
theorem rippleFrame (sub : Bool) (b n : ℕ) (x y : ℕ → ℕ) {p lo : ℕ}
(hl : lo ≤ b)
(hx : ∀ i < n, x i < p ∨ lo ≤ x i ∧ x i < b)
(hy : ∀ i < n, y i < p ∨ lo ≤ y i ∧ y i < b) :
GateFrame (rippleCircuit sub b n x y) p lo (b+8*n+1) := by
have hl' (k : ℕ) (hk : b ≤ k) (hq : k < b+8*n+1) :
k < p ∨ lo ≤ k ∧ k < b+8*n+1 := .inr ⟨hl.trans hk,hq⟩
intro g hg k hk
rcases List.mem_cons.mp hg with rfl | hg
· simp [Gate.names,RobsonCNF.Gate.names,rippleCarryWire] at hk
subst k
exact hl' b le_rfl (by omega)
· obtain ⟨i,hi,hg⟩ := List.mem_flatMap.mp hg
have hi' := List.mem_range.mp hi
have h1 := hx i hi'
have h2 := hy i hi'
have h1' : x i < p ∨ lo ≤ x i ∧ x i < b+8*n+1 := by omega
have h2' : y i < p ∨ lo ≤ y i ∧ y i < b+8*n+1 := by omega
simp only [rippleStep,List.mem_cons,List.mem_nil_iff,or_false] at hg
rcases hg with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;>
cases sub <;>
simp [Gate.names,RobsonCNF.Gate.names,rippleCarryWire,rippleXorWire,rippleBitWire] at hk <;> (repeat' first | subst k | rcases hk with hk | hk) <;>
first
| omega
| exact hl' (b+8*i+3) (by omega) (by omega)
| exact hl' (b+8*i+4) (by omega) (by omega)
| exact hl' (b+8*i+5) (by omega) (by omega)
| exact hl' (b+8*i+6) (by omega) (by omega)
theorem BinaryPort.addGates_frame (z b : ℕ) (x y : BinaryPort) {p lo : ℕ}
(hz : z < p) (hl : lo ≤ b) (hx : x.InFrame p lo b) (hy : y.InFrame p lo b) :
GateFrame (x.addGates z b y) p lo (x.addEnd b y) :=
rippleFrame false b (x.addWidth y) _ _ hl (x.padded_frame hx hz) (y.padded_frame hy hz)
theorem BinaryPort.addGates_extend (z b : ℕ) (x y : BinaryPort) (a : Assignment)
(hz : z < b) (hx : x.Below b) (hy : y.Below b) :
∃ c, Keeps a c b (x.addEnd b y) ∧ GateSat c (x.addGates z b y) := by
apply rippleCircuit_extends_interval
· intro i hi
change (if i < x.width then x.bit i else z) < b
split
· exact hx i (by assumption)
· exact hz
· intro i hi
change (if i < y.width then y.bit i else z) < b
split
· exact hy i (by assumption)
· exact hz
def BinaryPort.subPort (b : ℕ) (x y : BinaryPort) : BinaryPort :=
⟨x.addWidth y,monusOutWire b (x.addWidth y)⟩
def BinaryPort.subGates (z b : ℕ) (x y : BinaryPort) : List Gate :=
let k := x.addWidth y
monusCircuit b k (x.padded z k).bit (y.padded z k).bit
def BinaryPort.subEnd (b : ℕ) (x y : BinaryPort) : ℕ := b+9*x.addWidth y+2
theorem BinaryPort.subPort_names (b : ℕ) (x y : BinaryPort) {i : ℕ}
(hi : i < (x.subPort b y).width) :
b ≤ (x.subPort b y).bit i ∧ (x.subPort b y).bit i < x.subEnd b y := by
simp only [BinaryPort.subPort,BinaryPort.subEnd,monusOutWire] at hi ⊢
omega
theorem BinaryPort.subGates_exact (z b : ℕ) (x y : BinaryPort) (a : Assignment)
(hz : a z=false) (h : GateSat a (x.subGates z b y)) :
(x.subPort b y).value a = x.value a-y.value a := by
have q := monusCircuit_exact b (x.addWidth y) (x.padded z _).bit (y.padded z _).bit a h
change (x.subPort b y).value a = (x.padded z (x.addWidth y)).value a -
(y.padded z (x.addWidth y)).value a at q
rw [x.padded_value hz (show x.width ≤ x.addWidth y from le_max_left ..),
y.padded_value hz (show y.width ≤ x.addWidth y from le_max_right ..)] at q
exact q
theorem BinaryPort.subGates_frame (z b : ℕ) (x y : BinaryPort) {p lo : ℕ}
(hz : z < p) (hl : lo ≤ b) (hx : x.InFrame p lo b) (hy : y.InFrame p lo b) :
GateFrame (x.subGates z b y) p lo (x.subEnd b y) := by
let n := x.addWidth y
have h : GateFrame (rippleCircuit true b n (x.padded z n).bit (y.padded z n).bit)
p lo (b+8*n+1) := rippleFrame true b n _ _ hl (x.padded_frame hx hz) (y.padded_frame hy hz)
apply GateFrame.append.mpr
refine ⟨h.mono le_rfl le_rfl (by unfold BinaryPort.subEnd n; omega),?_⟩
intro g hg k hk
simp only [monusMask,List.mem_cons,List.mem_map] at hg
rcases hg with rfl | ⟨i,hi,rfl⟩
· simp [Gate.names,RobsonCNF.Gate.names,monusMaskWire,rippleCarryWire] at hk
unfold BinaryPort.subEnd
omega
· have hi' := List.mem_range.mp hi
simp [Gate.names,RobsonCNF.Gate.names,monusMaskWire,monusOutWire,rippleBitWire] at hk
unfold BinaryPort.subEnd
omega
theorem BinaryPort.subGates_extend (z b : ℕ) (x y : BinaryPort) (a : Assignment)
(hz : z < b) (hx : x.Below b) (hy : y.Below b) :
∃ c, Keeps a c b (x.subEnd b y) ∧ GateSat c (x.subGates z b y) := by
apply monusCircuit_extends_interval
· intro i hi
change (if i < x.width then x.bit i else z) < b
split
· exact hx i (by assumption)
· exact hz
· intro i hi
change (if i < y.width then y.bit i else z) < b
split
· exact hy i (by assumption)
· exact hz
end CNFEncComplexity.Robson
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).