Shared trace and gate interfaces for Robson’s reduction
DefinitionCNFEncComplexity_RobsonConstraintscomplexity-theoryramsat
The interface for a CNF encoding of a bit-cost nondeterministic RAM. Each possible aligned dyadic interval has named Boolean ports for occupancy, a possible input symbol, and up to three memory observations. The mathematical tests verify the original instruction trace and time bound, memory consistency, and sequential input consistency. Each gate list constrains the common ports and has separate auxiliary variables. The bounded generator predicate records exact satisfiability under a given port assignment, a polynomial-time construction, and a gate budget proportional to the time bound times its binary length.
Definition code
import Definitions.Def_CNFEncComplexity_AcceptsWithin
import Definitions.Def_CNFEncComplexity_enc
import Definitions.Def_CNFEncComplexity_encRobsonIn
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Option
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.Group.List.Basic
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.List.Sort
import Mathlib.Data.Nat.Size
import Mathlib.Logic.Function.Basic
import Mathlib.Tactic.Ring
namespace CNFEncComplexity.RobsonCNF
open CookLevin Turing.MultiTapeTM
/-- One local Boolean relation. Gates constrain named wires and need not be listed in
topological order. An asserted clause may have arbitrary width. -/
inductive Gate where
| pin (out : ℕ) (value : Bool)
| copy (out src : ℕ)
| inv (out src : ℕ)
| conj (out left right : ℕ)
| disj (out left right : ℕ)
| parity (out left right : ℕ)
| mux (out sel yes no : ℕ)
| assert (clause : Clause)
def Gate.Holds (α : Assignment) : Gate → Prop
| .pin out value => α out = value
| .copy out src => α out = α src
| .inv out src => α out = !α src
| .conj out a b => α out = (α a && α b)
| .disj out a b => α out = (α a || α b)
| .parity out a b => α out = (α a ^^ α b)
| .mux out s a b => α out = (if α s then α a else α b)
| .assert clause => satisfiesClause α clause = true
def Gate.code : Gate → List ℕ
| .pin out false => [0,out]
| .pin out true => [1,out]
| .copy out a => [2,out,a]
| .inv out a => [3,out,a]
| .conj out a b => [4,out,a,b]
| .disj out a b => [5,out,a,b]
| .parity out a b => [6,out,a,b]
| .mux out s a b => [7,out,s,a,b]
| .assert clause => 8 :: clauseN clause
private def decodeGate : List ℕ → Gate
| [0,out] => .pin out false
| [1,out] => .pin out true
| [2,out,a] => .copy out a
| [3,out,a] => .inv out a
| [4,out,a,b] => .conj out a b
| [5,out,a,b] => .disj out a b
| [6,out,a,b] => .parity out a b
| [7,out,s,a,b] => .mux out s a b
| 8 :: ns => .assert (nClause ns)
| _ => .assert []
theorem Gate.code_injective : Function.Injective Gate.code := by
apply Function.LeftInverse.injective (g := decodeGate)
intro g
cases g with
| pin out b => cases b <;> rfl
| copy => rfl
| inv => rfl
| conj => rfl
| disj => rfl
| parity => rfl
| mux => rfl
| assert => simp [Gate.code, decodeGate]
def gateEnc : Gate ↪ List Bool :=
(⟨Gate.code, Gate.code_injective⟩ : Gate ↪ List ℕ).trans (encList encUnary)
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]
def robsonWords (a : List Instr × ℕ × ℕ) : List (List Bool) :=
[unaryWord a.2.1,unaryWord a.2.2] ++ progWords a.1
end CNFEncComplexity.RobsonCNF
namespace CNFEncComplexity.Robson
open CookLevin RobsonCNF Turing.MultiTapeTM
/-- A single external memory access. Reads validate their alleged value, and writes replace
the value at the given address. -/
structure MemoryAccess where
address : ℕ
value : ℕ
writes : Bool
deriving DecidableEq
abbrev Memory := ℕ → ℕ
def MemoryAccess.read (address value : ℕ) : MemoryAccess := ⟨address, value, false⟩
def MemoryAccess.write (address value : ℕ) : MemoryAccess := ⟨address, value, true⟩
/-- A validated read rewrites the same value, so the replay fold may update the register on
both kinds of event. This keeps both projections and the sorted certificate uniform. -/
def replay : Memory → List MemoryAccess → Memory
| current, [] => current
| current, e :: es => replay (Function.update current e.address e.value) es
def memoryValid : Memory → List MemoryAccess → Prop
| _, [] => True
| current, e :: es => (e.writes = true ∨ current e.address = e.value) ∧
memoryValid (Function.update current e.address e.value) es
/-- A packet contains the external interactions of one instruction, together with
its exact charge in the nondeterministic RAM model. -/
structure Packet where
input : Option ℕ
accesses : List MemoryAccess
cost : ℕ
def Packet.inputValid (p : Packet) (w : List Bool) (head : ℕ) : Prop :=
match p.input with
| none => True
| some v => v = readSym w head
def Packet.nextHead (p : Packet) (head : ℕ) : ℕ :=
if p.input.isSome then head + 1 else head
/-- A locally correct instruction, with the values returned by memory replaced by
witnesses. Program control and the exact logarithmic charge are still checked. -/
inductive PacketStep (prog : List Instr) : ℕ → ℕ → Packet → Prop where
| loadc {pc v : ℕ} (h : prog[pc]? = some (.loadc v)) :
PacketStep prog pc (pc + 1) ⟨none, [.write 0 v], 1 + bitLen v⟩
| load {pc j a : ℕ} (h : prog[pc]? = some (.load j)) :
PacketStep prog pc (pc + 1) ⟨none, [.read j a, .write 0 a], 1 + bitLen j + bitLen a⟩
| loadi {pc j a b : ℕ} (h : prog[pc]? = some (.loadi j)) :
PacketStep prog pc (pc + 1)
⟨none, [.read j a, .read a b, .write 0 b], 1 + bitLen j + bitLen a + bitLen b⟩
| store {pc j a : ℕ} (h : prog[pc]? = some (.store j)) :
PacketStep prog pc (pc + 1) ⟨none, [.read 0 a, .write j a], 1 + bitLen j + bitLen a⟩
| storei {pc j a b : ℕ} (h : prog[pc]? = some (.storei j)) :
PacketStep prog pc (pc + 1)
⟨none, [.read j a, .read 0 b, .write a b], 1 + bitLen j + bitLen a + bitLen b⟩
| add {pc j a b : ℕ} (h : prog[pc]? = some (.add j)) :
PacketStep prog pc (pc + 1)
⟨none, [.read 0 a, .read j b, .write 0 (a + b)], 1 + bitLen j + bitLen a + bitLen b⟩
| sub {pc j a b : ℕ} (h : prog[pc]? = some (.sub j)) :
PacketStep prog pc (pc + 1)
⟨none, [.read 0 a, .read j b, .write 0 (a - b)], 1 + bitLen j + bitLen a + bitLen b⟩
| read {pc v : ℕ} (h : prog[pc]? = some .read) :
PacketStep prog pc (pc + 1) ⟨some v, [.write 0 v], 1 + bitLen v⟩
| jump {pc l : ℕ} (h : prog[pc]? = some (.jump l)) :
PacketStep prog pc l ⟨none, [], 1 + bitLen l⟩
| jzeroTaken {pc l : ℕ} (h : prog[pc]? = some (.jzero l)) :
PacketStep prog pc l ⟨none, [.read 0 0], 1 + bitLen l + bitLen 0⟩
| jzeroNotTaken {pc l a : ℕ} (h : prog[pc]? = some (.jzero l)) (ha : a ≠ 0) :
PacketStep prog pc (pc + 1) ⟨none, [.read 0 a], 1 + bitLen l + bitLen a⟩
| njumpLeft {pc l₁ l₂ : ℕ} (h : prog[pc]? = some (.njump l₁ l₂)) :
PacketStep prog pc l₁ ⟨none, [], 1 + bitLen l₁ + bitLen l₂⟩
| njumpRight {pc l₁ l₂ : ℕ} (h : prog[pc]? = some (.njump l₁ l₂)) :
PacketStep prog pc l₂ ⟨none, [], 1 + bitLen l₁ + bitLen l₂⟩
def packetAccesses (ps : List Packet) : List MemoryAccess :=
ps.flatMap Packet.accesses
/-- Check only local instruction packets, without using a RAM store. -/
inductive PacketTrace (prog : List Instr) (w : List Bool) :
ℕ → ℕ → ℕ → ℕ → List Packet → ℕ → Prop where
| nil (pc h : ℕ) : PacketTrace prog w pc h pc h [] 0
| cons {pc h next fin last k : ℕ} {p : Packet} {ps : List Packet} :
PacketStep prog pc next p → p.inputValid w h →
PacketTrace prog w next (p.nextHead h) fin last ps k →
PacketTrace prog w pc h fin last (p :: ps) (p.cost + k)
/-- The least power-of-two width that can hold a step of the indicated cost. -/
def slotLevel (cost : ℕ) : ℕ := (cost-1).size
def slotWidth (cost : ℕ) : ℕ := 2^(slotLevel cost)
/-- Round a cursor up to a multiple of a positive slot width. -/
def alignedStart (cursor width : ℕ) : ℕ := (cursor+width-1)/width*width
/-- Nonoverlapping aligned time slots for a sequence of positive-cost transitions. -/
inductive Starts : ℕ → List ℕ → List ℕ → Prop
| nil (cursor : ℕ) : Starts cursor [] []
| cons {cursor cost start : ℕ} {costs starts : List ℕ} :
cursor ≤ start → slotWidth cost ∣ start →
Starts (start+slotWidth cost) costs starts →
Starts cursor (cost::costs) (start::starts)
def accessWeight (e : MemoryAccess) : ℕ := bitLen e.address + bitLen e.value
def accessWork (trace : List MemoryAccess) : ℕ :=
(trace.map accessWeight).sum
/-- A write retires the prior value, which need not be charged by that source
instruction. Reads create no retired record. -/
def retiredWeight (m : Memory) : List MemoryAccess → ℕ
| [] => 0
| a::as =>
(if a.writes then (m a.address).size else 0) +
retiredWeight (Function.update m a.address a.value) as
/-- Include space for packet operands and for overwritten values in the schedule.
The separate packet cost still records precisely what the source machine charges. -/
def scheduleCharges (m : Memory) : List Packet → List ℕ
| [] => []
| p::ps =>
(p.cost+accessWork p.accesses+retiredWeight m p.accesses) ::
scheduleCharges (replay m p.accesses) ps
/-- A final packet reads the accumulator as one and uses the original halt cost. -/
def finalPacket : Packet := ⟨none,[.read 0 1],1+bitLen 1⟩
/-- The control path can be checked before checking the input stream and memory. -/
inductive PacketPath (prog : List Instr) : ℕ → ℕ → List Packet → ℕ → Prop
| nil (pc : ℕ) : PacketPath prog pc pc [] 0
| cons {pc next fin k : ℕ} {p : Packet} {ps : List Packet} :
PacketStep prog pc next p → PacketPath prog next fin ps k →
PacketPath prog pc fin (p::ps) (p.cost+k)
def packetInputs (ps : List Packet) : List ℕ := ps.filterMap Packet.input
def inputPrefix (w : List Bool) (head len : ℕ) : List ℕ :=
(List.range len).map (fun i => readSym w (head+i))
/-- Represent a chronological memory row together with its explicit old value. The
old value in a read is ignored. -/
structure ObservedAccess where
action : MemoryAccess
old : ℕ
def observedMemoryValid (m : Memory) : List ObservedAccess → Prop
| [] => True
| row::rows => m row.action.address = (if row.action.writes then row.old else row.action.value) ∧
observedMemoryValid (Function.update m row.action.address row.action.value) rows
/-- The nonoverlapping slot structure, exact original clock, and independently
checkable logs of both input and memory. -/
def TimedObservation (prog : List Instr) (w : List Bool) (t : ℕ) : Prop :=
let H := slotLevel (4*(9*t+1))
∃ (fin k : ℕ) (ps : List Packet) (reads : List ℕ) (observed : List ObservedAccess),
PacketPath prog 0 fin ps k ∧ prog[fin]? = some .halt ∧
k+(1+bitLen 1) ≤ t ∧ packetInputs ps = reads ∧
packetAccesses (ps++[finalPacket]) = observed.map ObservedAccess.action ∧
observedMemoryValid (fun _ => 0) observed ∧
reads = inputPrefix (w.take t) 0 reads.length ∧
let costs := scheduleCharges (fun _ => 0) (ps++[finalPacket])
costs.sum ≤ 9*t ∧
∃ 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])
def layoutHeight (t : ℕ) : ℕ := slotLevel (4*(9*t+1))
def layoutHorizon (t : ℕ) : ℕ := 2^layoutHeight t
/-- All aligned slots in start-time order. Slots with a common start appear in width
order. A valid schedule may activate at most one of them. -/
def layoutSlots (t : ℕ) : List (ℕ × ℕ) :=
(List.range (layoutHorizon t)).flatMap fun a =>
(((List.range (layoutHeight t+1)).filter fun j => a % 2^j = 0).map (a,·))
/-- Reserve initial variables for the original input, then a rectangular namespace
for the finitely many shared trace fields. Only aligned slots use this namespace. -/
def sharedLimit (n t : ℕ) : ℕ :=
n+layoutHorizon t*(layoutHeight t+1)*19*layoutHorizon t
def port (n t : ℕ) (slot : ℕ × ℕ) (field bit : ℕ) : ℕ :=
n+(((slot.1*(layoutHeight t+1)+slot.2)*19+field)*layoutHorizon t+bit)
def portWord (α : Assignment) (n t : ℕ) (slot : ℕ × ℕ) (field : ℕ) : ℕ :=
((List.range (2^slot.2)).map fun bit => (α (port n t slot field bit)).toNat*2^bit).sum
def portInput (α : Assignment) (n t : ℕ) (slot : ℕ × ℕ) : Option ℕ :=
if α (port n t slot 0 0) then
some ((α (port n t slot 1 0)).toNat+2*(α (port n t slot 2 0)).toNat)
else none
def portMemory (α : Assignment) (n t : ℕ) (slot : ℕ × ℕ) (i : ℕ) : Option ObservedAccess :=
let f := 3+5*i
if α (port n t slot f 0) then
some ⟨⟨portWord α n t slot (f+2),portWord α n t slot (f+3),α (port n t slot (f+1) 0)⟩,
portWord α n t slot (f+4)⟩
else none
def readStream (α : Assignment) (n t : ℕ) : List ℕ :=
(layoutSlots t).filterMap (portInput α n t)
def memoryStream (α : Assignment) (n t : ℕ) : List ObservedAccess :=
(layoutSlots t).flatMap fun s => (List.range 3).filterMap (portMemory α n t s)
def inputTape (α : Assignment) (n : ℕ) : List Bool := List.ofFn (fun i : Fin n => α i.val)
def slotRows (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) : List ObservedAccess :=
(List.range 3).filterMap (portMemory α n t s)
def slotLive (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) : Bool := α (port n t s 18 0)
def liveSlots (α : Assignment) (n t : ℕ) : List (ℕ × ℕ) :=
(layoutSlots t).filter (slotLive α n t)
/-- Occupied intervals are disjoint in chronological order, and empty intervals
carry no external requests. -/
def SlotsWellFormed (α : Assignment) (n t : ℕ) : Prop :=
(liveSlots α n t).Pairwise (fun s r => s.1+2^s.2 ≤ r.1) ∧
∀ s ∈ layoutSlots t, slotLive α n t s = false →
portInput α n t s = none ∧ slotRows α n t s = []
def Packet.ports (p : Packet) : Option ℕ × List MemoryAccess := (p.input,p.accesses)
def slotView (α : Assignment) (n t : ℕ) (s : ℕ × ℕ) : Option ℕ × List MemoryAccess :=
(portInput α n t s,(slotRows α n t s).map ObservedAccess.action)
def HasSlottedPath (prog : List Instr) (n t : ℕ) (α : Assignment) : Prop :=
∃ fin k ps, PacketPath prog 0 fin ps k ∧ prog[fin]? = some .halt ∧
k+(1+bitLen 1) ≤ t ∧
(ps++[finalPacket]).map Packet.ports = (liveSlots α n t).map (slotView α n t)
/-- The tests share names only for the raw trace and original input. Both RAM
components can independently reject an ill-formed interval layout. -/
def Checks (part : Fin 3) (prog : List Instr) (n t : ℕ) (α : Assignment) : Prop :=
if part.val = 0 then SlotsWellFormed α n t ∧ HasSlottedPath prog n t α
else if part.val = 1 then SlotsWellFormed α n t ∧ observedMemoryValid (fun _ => 0) (memoryStream α n t)
else readStream α n t = inputPrefix (inputTape α n) 0 (readStream α n t).length
def Gate.names : Gate → List ℕ
| .pin a _ => [a]
| .copy a b | .inv a b => [a,b]
| .conj a b c | .disj a b c | .parity a b c => [a,b,c]
| .mux a b c d => [a,b,c,d]
| .assert cs => cs.map Literal.var
def owns (base : ℕ) (part : Fin 3) (r : ℕ) : Prop :=
r < base ∨ (r-base)%3 = part.val
/-- Each gate subsystem uses the common interface and a disjoint set of fresh names.
The extension law is an exact semantic interface for supplying the common bits. -/
def ExtendsWith (base : ℕ) (gates : List Gate) (α : Assignment) : Prop :=
∃ β : Assignment, (∀ r < base, β r = α r) ∧ (∀ g ∈ gates, g.Holds β)
/-- One of the three uniform gate generators. Auxiliary names are private to
their component, so arbitrary assignments at the shared ports can be extended
independently. -/
def GateComponent (P : ℕ) (part : Fin 3) : Prop :=
∃ (C : ℕ) (gen : List (List Bool) → List Gate),
ComputableInPolyTime gen (encList encBits) (encList gateEnc) ∧
∀ (prog : List Instr) (n t : ℕ), prog.length ≤ P →
let gates := gen (robsonWords (prog,n,t))
gates.length ≤ C*(t+1)*(t.size+1) ∧
(∀ g ∈ gates, ∀ r ∈ Gate.names g, owns (sharedLimit n t) part r) ∧
∀ α, ExtendsWith (sharedLimit n t) gates α ↔ Checks part prog n t α
/-- Every accepting execution can fill the shared ports of the fixed dyadic layout. -/
def HasCompletePorts : Prop :=
∀ (prog : List Instr) (n t : ℕ) (x : Fin n → Bool),
AcceptsWithin prog (List.ofFn x) t →
∃ α : Assignment, (∀ i : Fin n, α i.val = x i) ∧ ∀ j : Fin 3, Checks j prog n t α
end CNFEncComplexity.Robson
Source
Robson, An O(T log T) reduction from RAM computations to satisfiability, TCS 82 (1991), pp. 141–149, Sections 2–3, https://www.sciencedirect.com/science/article/pii/0304397591901774. Shared-slot interface for the RAM model of Krapivin–Przybocki–Subercaseaux, arXiv:2611.05614, Section 3, Theorem 10.