Fused single-pass evaluation scan for unary-encoded CNF strings
DefinitionCookLevin_evalScanWe define a single-pass left-to-right evaluator for the unary-encoded CNF strings of the Cook-Levin encoding. A marker true introduces a new clause (formula level) or a new literal number (clause level); a maximal run of trues terminated by false encodes a natural number; false terminates the current list. The automaton scanAux threads a control mode (formula, clause, literal), a clause accumulator (OR over literals), a formula accumulator (AND over completed clauses), and a unary counter, consuming the string once. When the string ends, pending literals and clauses close exactly as the fuel decoder decodeFormulaNFuel closes them. The top-level evaluation evalScan x w returns the verdict of the CNF string x under the raw certificate bits w, where odd literal numbers are positive bits (Pos n/2 reads bit n/2 of w) and even numbers are negated bits (Neg n/2). The definition is the control-flow mirror of the evaluating Turing machine and is structurally recursive in the string.
import Definitions.Def_CookLevin_Verifier
/-!
# Cook–Levin evaluation scan (fused single-pass CNF evaluation)
A single-pass evaluator for the unary-encoded CNF strings of
`Def_CookLevin_Satisfiability`. The string grammar is greedy
left-to-right: a marker `true` introduces a new clause (formula level) or a
new literal number (clause level), a maximal run of `true`s terminated by
`false` encodes a number, and `false` terminates the current list.
`scanAux` fuses the evaluation into a single left-to-right pass over the
string, mirroring the control flow of the evaluating Turing machine: the
mode is the control state, `cnt` the unary counter, `c` and `f` the clause
and formula accumulators. When the string ends, pending structures close
exactly as the fuel decoder `decodeFormulaNFuel` closes them.
-/
namespace CookLevin
/-- Literal value of the literal number `n` under the raw certificate bits
`w`: odd numbers are `Pos n/2` (bit `n/2` of `w`), even numbers are
`Neg n/2` (the negated bit); out-of-range bits are `false`. -/
def litValN (w : List Bool) (n : Nat) : Bool :=
if n % 2 = 1 then w.getD (n / 2) false else !(w.getD (n / 2) false)
/-- Control mode of the evaluation scan: scanning the formula, a clause,
or the unary number of a literal. -/
inductive ScanMode
| formula | clause | lit
/-- The single-pass evaluation automaton. Arguments: certificate bits
`w`, control mode, clause accumulator `c` (OR over the literals of the
current clause so far), formula accumulator `f` (AND over completed
clauses), unary counter `cnt` of the literal being read, and the remaining
string. A `false` terminates the current list; the empty string closes
all pending literals and clauses. -/
def scanAux (w : List Bool) : ScanMode → Bool → Bool → Nat → List Bool → Bool
-- the string ends: close pending structures
| .formula, _, f, _, [] => f
| .clause, c, f, _, [] => f && c
| .lit, c, f, cnt, [] => f && (c || litValN w cnt)
-- formula level
| .formula, _, f, _, false :: _ => f
| .formula, _, f, _, true :: rest => scanAux w .clause false f 0 rest
-- clause level
| .clause, c, f, _, false :: rest => scanAux w .formula c (f && c) 0 rest
| .clause, c, f, _, true :: rest => scanAux w .lit c f 0 rest
-- literal level
| .lit, c, f, cnt, false :: rest =>
scanAux w .clause (c || litValN w cnt) f 0 rest
| .lit, c, f, cnt, true :: rest => scanAux w .lit c f (cnt + 1) rest
/-- The verdict of the single-pass evaluation scan of the CNF string `x`
under the certificate bits `w`. -/
def evalScan (x w : List Bool) : Bool := scanAux w .formula false true 0 x
end CookLevin