While this submission is a draft, it cannot be used by other submissions.

Word encoding of a (3,4) formula

Lax470956.Exact34Encoding · concepts/Lax470956/Exact34Encoding.lean · lax-470956

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A (3,4)(3,4) 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
    4 concepts; 2 descendants hidden
    100%
    Proven claimOpen claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax470956.ParameterizedComplexity
    2
    3/-!
    4---
    5title: Word encoding of a (3,4) formula
    6type: definition
    7---
    8A (3,4)(3,4) formula is handed to a word random access machine as a word of numbers:
    9the number of variables, the number of clauses, then three blocks of three numbers per
    10clause, one block per literal, giving the variable it mentions, whether the occurrence is
    11positive, 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
    16two halves of the theorem actually use. `app_inj` — distinct occurrences of one variable
    17carry distinct appearance indices — is what the *correctness* of the reduction needs: it
    18makes 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
    20word, a two-entry word could declare 21002^{100} variables, and the reduction would have to
    21emit that many jobs. Requiring surjectivity of the appearance index would give both, and
    22more than either needs.
    23
    24The appearance index is part of the input rather than something a reader computes. It is
    25what the reduction of Theorem 2 turns into a deadline, and requiring it to be supplied
    26and to be consistent is what makes the deadlines of one variable's occurrences distinct.
    27That all four indices actually occur is never used, and is not required here; what is
    28required instead is the weaker `var_le`, which is the part of the counting a reduction
    29running in bounded time cannot do without.
    30
    31A formula is presented directly, not as a satisfying assignment or any other certificate:
    32the yes-instances are the satisfiable words, and satisfiability is quantified over
    33assignments to the variables the word declares.
    34
    35Sign bits are numbers, `1` for a positive occurrence and anything else for a negative
    36one, because a word RAM holds numbers. Reading a sign is then a comparison, as the emitted machine does.
    37-/
    38
    39namespace Lax470956.Exact34Encoding
    40
    41/-- The number of variables declared by a word: its first entry. -/
    42def varCount (x : List ℕ) : ℕ := x.getD 0 0
    43
    44/-- The number of clauses declared by a word: its second entry. -/
    45def clauseCount (x : List ℕ) : ℕ := x.getD 1 0
    46
    47/-- The variable of literal `h` of clause `c`. -/
    48def 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. -/
    51def 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. -/
    54def 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
    57numbers per clause, every variable in range, every appearance index below four,
    58distinct occurrences of one variable carrying distinct appearance indices, and no more
    59variables declared than there are literal slots to hold them. -/
    60structure 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
    75agrees with `τ`. -/
    76def 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. -/
    80def Formulas : Set (List ℕ) := {x | WellFormed x}
    81
    82/-- **(3,4)-SAT**, as a set of words. -/
    83def Satisfiable : Set (List ℕ) := {x | WellFormed x ∧ ∃ τ, Satisfies x τ}
    84
    85end 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. appinjapp_inj — 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. varlevar_le 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 21002^{100} 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 varlevar_le, 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, 11 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.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…