Word encoding of a (3,4) formula
Lax470956.Exact34Encoding · concepts/Lax470956/Exact34Encoding.lean · lax-470956
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A formula is handed to a word random access machine as a word of numbers: the number of variables, the number of clauses, then three blocks of three numbers per clause, one block per literal, giving the variable it mentions, whether the occurrence is positive, and which of the four occurrences of that variable it is.
Concept map
Lean source view on GitHub
| 1 | import Lax470956.ParameterizedComplexity |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Word encoding of a (3,4) formula |
| 6 | type: definition |
| 7 | --- |
| 8 | A formula is handed to a word random access machine as a word of numbers: |
| 9 | the number of variables, the number of clauses, then three blocks of three numbers per |
| 10 | clause, one block per literal, giving the variable it mentions, whether the occurrence is |
| 11 | positive, and which of the four occurrences of that variable it is. |
| 12 | |
| 13 | # Formalization notes |
| 14 | |
| 15 | "Every variable occurs at most four times" is split into the two consequences the |
| 16 | two halves of the theorem actually use. `app_inj` — distinct occurrences of one variable |
| 17 | carry distinct appearance indices — is what the *correctness* of the reduction needs: it |
| 18 | makes the deadlines of one variable's occurrences pairwise distinct. `var_le` is what its |
| 19 | *running time* needs: without a bound tying the number of variables to the length of the |
| 20 | word, a two-entry word could declare variables, and the reduction would have to |
| 21 | emit that many jobs. Requiring surjectivity of the appearance index would give both, and |
| 22 | more than either needs. |
| 23 | |
| 24 | The appearance index is part of the input rather than something a reader computes. It is |
| 25 | what the reduction of Theorem 2 turns into a deadline, and requiring it to be supplied |
| 26 | and to be consistent is what makes the deadlines of one variable's occurrences distinct. |
| 27 | That all four indices actually occur is never used, and is not required here; what is |
| 28 | required instead is the weaker `var_le`, which is the part of the counting a reduction |
| 29 | running in bounded time cannot do without. |
| 30 | |
| 31 | A formula is presented directly, not as a satisfying assignment or any other certificate: |
| 32 | the yes-instances are the satisfiable words, and satisfiability is quantified over |
| 33 | assignments to the variables the word declares. |
| 34 | |
| 35 | Sign bits are numbers, `1` for a positive occurrence and anything else for a negative |
| 36 | one, because a word RAM holds numbers. Reading a sign is then a comparison, as the emitted machine does. |
| 37 | -/ |
| 38 | |
| 39 | namespace Lax470956.Exact34Encoding |
| 40 | |
| 41 | /-- The number of variables declared by a word: its first entry. -/ |
| 42 | def varCount (x : List ℕ) : ℕ := x.getD 0 0 |
| 43 | |
| 44 | /-- The number of clauses declared by a word: its second entry. -/ |
| 45 | def clauseCount (x : List ℕ) : ℕ := x.getD 1 0 |
| 46 | |
| 47 | /-- The variable of literal `h` of clause `c`. -/ |
| 48 | def litVar (x : List ℕ) (c h : ℕ) : ℕ := x.getD (2 + 9 * c + 3 * h) 0 |
| 49 | |
| 50 | /-- The sign of literal `h` of clause `c`: `1` when the occurrence is positive. -/ |
| 51 | def litSign (x : List ℕ) (c h : ℕ) : ℕ := x.getD (2 + 9 * c + 3 * h + 1) 0 |
| 52 | |
| 53 | /-- Which of the four occurrences of its variable literal `h` of clause `c` is. -/ |
| 54 | def litApp (x : List ℕ) (c h : ℕ) : ℕ := x.getD (2 + 9 * c + 3 * h + 2) 0 |
| 55 | |
| 56 | /-- The word `x` is a `(3,4)` formula: two header entries followed by nine |
| 57 | numbers per clause, every variable in range, every appearance index below four, |
| 58 | distinct occurrences of one variable carrying distinct appearance indices, and no more |
| 59 | variables declared than there are literal slots to hold them. -/ |
| 60 | structure WellFormed (x : List ℕ) : Prop where |
| 61 | /-- The word consists of the header and three numbers per literal. -/ |
| 62 | length_eq : x.length = 2 + 9 * clauseCount x |
| 63 | /-- Every literal mentions a declared variable. -/ |
| 64 | var_lt : ∀ c < clauseCount x, ∀ h < 3, litVar x c h < varCount x |
| 65 | /-- Every appearance index is one of four. -/ |
| 66 | app_lt : ∀ c < clauseCount x, ∀ h < 3, litApp x c h < 4 |
| 67 | /-- Every declared variable occurs in some clause. There are `3C` literal slots, so a |
| 68 | formula in which every variable occurs has at most `3C` of them. -/ |
| 69 | var_le : varCount x ≤ 3 * clauseCount x |
| 70 | /-- Distinct occurrences of one variable carry distinct appearance indices. -/ |
| 71 | app_inj : ∀ c < clauseCount x, ∀ h < 3, ∀ c' < clauseCount x, ∀ h' < 3, |
| 72 | litVar x c h = litVar x c' h' → litApp x c h = litApp x c' h' → c = c' ∧ h = h' |
| 73 | |
| 74 | /-- The assignment `τ` satisfies the formula `x`: every clause owns a literal whose sign |
| 75 | agrees with `τ`. -/ |
| 76 | def Satisfies (x : List ℕ) (τ : ℕ → Bool) : Prop := |
| 77 | ∀ c < clauseCount x, ∃ h < 3, (litSign x c h = 1) = τ (litVar x c h) |
| 78 | |
| 79 | /-- The words encoding a `(3,4)` formula. -/ |
| 80 | def Formulas : Set (List ℕ) := {x | WellFormed x} |
| 81 | |
| 82 | /-- **(3,4)-SAT**, as a set of words. -/ |
| 83 | def Satisfiable : Set (List ℕ) := {x | WellFormed x ∧ ∃ τ, Satisfies x τ} |
| 84 | |
| 85 | end Lax470956.Exact34Encoding |
| 86 |
Formalization notes
"Every variable occurs at most four times" is split into the two consequences the two halves of the theorem actually use. — distinct occurrences of one variable carry distinct appearance indices — is what the correctness of the reduction needs: it makes the deadlines of one variable's occurrences pairwise distinct. is what its running time needs: without a bound tying the number of variables to the length of the word, a two-entry word could declare variables, and the reduction would have to emit that many jobs. Requiring surjectivity of the appearance index would give both, and more than either needs.
The appearance index is part of the input rather than something a reader computes. It is what the reduction of Theorem 2 turns into a deadline, and requiring it to be supplied and to be consistent is what makes the deadlines of one variable's occurrences distinct. That all four indices actually occur is never used, and is not required here; what is required instead is the weaker , which is the part of the counting a reduction running in bounded time cannot do without.
A formula is presented directly, not as a satisfying assignment or any other certificate: the yes-instances are the satisfiable words, and satisfiability is quantified over assignments to the variables the word declares.
Sign bits are numbers, for a positive occurrence and anything else for a negative one, because a word RAM holds numbers. Reading a sign is then a comparison, as the emitted machine does.
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments