Sorting circuit for occupied-slot lookup
DefinitionCNFEncComplexity_MassProductionLookupcomplexity-theorysatisfiability
Gate and CNF generators for checking that each query matches an occupied slot in the mass-production layout.
Definition code
import Definitions.Def_CNFEncComplexity_RobsonMemoryWindowGates
namespace CNFEncComplexity.MassProduction
open CookLevin Robson RobsonCNF Turing.MultiTapeTM ComputableTidilyInPolyTime
/-- The first `b*n` input bits contain queries. Each remaining block contains a
slot word followed by its occupation bit. -/
def lookupInputs (n b q : ℕ) : ℕ := b*n + q*(n+1)
def lookupQueryBit (n i j : ℕ) : ℕ := i*n+j
def lookupSlotBit (n b r j : ℕ) : ℕ := b*n+r*(n+1)+j
def lookupHeight (b q : ℕ) : ℕ := (q+b).size
def lookupZero (n b q : ℕ) : ℕ := lookupInputs n b q+q
def lookupOne (n b q : ℕ) : ℕ := lookupZero n b q+1
def lookupScratch (n b q : ℕ) : ℕ := lookupZero n b q+2
def lookupBefore (n b q r : ℕ) : ℕ := lookupInputs n b q+r
def slotLane (n b q r k : ℕ) : ℕ :=
if k=0 then lookupSlotBit n b r n
else if k≤n then lookupSlotBit n b r (k-1)
else if k=n+1 then lookupBefore n b q r
else if k=2*n+2 then lookupOne n b q
else lookupZero n b q
def queryLane (n b q i k : ℕ) : ℕ :=
if k=0 ∨ k=n+1 ∨ k=2*n+2 then lookupOne n b q
else if k≤n then lookupQueryBit n i (k-1)
else lookupZero n b q
def lookupSource (n b q r k : ℕ) : ℕ :=
if r<q then slotLane n b q r k
else if r<q+b then queryLane n b q (r-q) k
else lookupZero n b q
def lookupGates (n b q : ℕ) : List Gate :=
[.pin (lookupZero n b q) false, .pin (lookupOne n b q) true] ++
memSortGates none n (lookupHeight b q) (lookupScratch n b q)
(fun i => lookupSource n b q i.val)
/-- `(b,n,q)` encodes the number of queries, the word width and the number of slots. -/
def lookupBuild (p : ℕ × ℕ × ℕ) : Formula := compile (lookupGates p.2.1 p.1 p.2.2)
abbrev lookupInputEnc := encPair encUnary (encPair encUnary encUnary)
end CNFEncComplexity.MassProduction
Source
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.