Documentation

DescriptiveComplexity.Problems.ThreeSat.FromSat

SAT reduces to 3SAT by an ordered FO reduction #

The classical clause-splitting reduction, as an ordered first-order reduction – DescriptiveComplexity.sat_ordered_fo_reduction_threeSat : SAT ≤ᶠᵒ[≤] ThreeSAT. Every clause of the input CNF is split along the linear order of its literal occurrences (DescriptiveComplexity.OccurrenceOrder) into a chain of clauses of width at most three, linked by fresh variables.

Concretely, the interpretation (DescriptiveComplexity.SatToThreeSat.satToThreeSat, tags SplitTag, dimension 2) produces, for each occurrence (x, s) of a clause c:

For a clause with occurrences ℓ₁ < ⋯ < ℓₖ, this yields the usual chain (ℓ₁ ∨ y₂), (¬y₂ ∨ ℓ₂ ∨ y₃), …, (¬yₖ ∨ ℓₖ). Empty input clauses are copied as empty clauses (.empty, (c, c)), keeping the output unsatisfiable. All other tuples are junk: they are neither clauses nor occur in any clause.

The two halves of correctness are SatToThreeSat.widthAtMostThree_map (the output always satisfies the width promise – each piece has at most three literals, by uniqueness of the successor occurrence) and SatToThreeSat.satisfiable_iff_map (satisfiability is preserved, by the usual chain argument, threaded along the occurrence order).

Tags for the clause-splitting interpretation of 3SAT instances in ordered CNF instances.

  • var : SplitTag

    (.var, (x, x)) is the copy of the propositional variable x.

  • piece (s : Bool) : SplitTag

    (.piece s, (c, x)) is the clause piece of the occurrence (x, s) of the clause c.

  • empty : SplitTag

    (.empty, (c, c)) is the copy of the empty clause c.

Instances For
    Equations
    Instances For

      Defining formula for satPosIn: the piece of a positive occurrence contains its literal positively, and every piece contains the linking variable of the successor occurrence (if any) positively.

      Equations
      Instances For

        Defining formula for satNegIn: the piece of a negative occurrence contains its literal negatively, and the piece of a non-first occurrence contains its own linking variable negatively.

        Equations
        Instances For

          The first-order interpretation producing, from an ordered CNF structure, its width-three split.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For

            Characterizations of the interpreted relations #

            @[simp]
            theorem DescriptiveComplexity.SatToThreeSat.posIn_iff {A : Type} [FirstOrder.Language.sat.Structure A] [LinearOrder A] (t₁ t₂ : SplitTag) (w₁ w₂ : Fin 2 → A) :
            FirstOrder.Language.Structure.RelMap FirstOrder.Language.satPosIn ![(t₁, w₁), (t₂, w₂)] ↔ t₁ = SplitTag.piece true ∧ t₂ = SplitTag.var ∧ (w₂ 0 = w₂ 1 ∧ w₂ 0 = w₁ 1) ∧ SatOcc.OccIn (w₁ 0) (w₁ 1) true ∨ ∃ (s : Bool) (t : Bool), t₁ = SplitTag.piece s ∧ t₂ = SplitTag.link t ∧ w₁ 0 = w₂ 0 ∧ SatOcc.SuccOcc (w₁ 0) (w₁ 1) s (w₂ 1) t
            @[simp]
            theorem DescriptiveComplexity.SatToThreeSat.negIn_iff {A : Type} [FirstOrder.Language.sat.Structure A] [LinearOrder A] (t₁ t₂ : SplitTag) (w₁ w₂ : Fin 2 → A) :
            FirstOrder.Language.Structure.RelMap FirstOrder.Language.satNegIn ![(t₁, w₁), (t₂, w₂)] ↔ t₁ = SplitTag.piece false ∧ t₂ = SplitTag.var ∧ (w₂ 0 = w₂ 1 ∧ w₂ 0 = w₁ 1) ∧ SatOcc.OccIn (w₁ 0) (w₁ 1) false ∨ ∃ (s : Bool), t₁ = SplitTag.piece s ∧ t₂ = SplitTag.link s ∧ (w₁ 0 = w₂ 0 ∧ w₁ 1 = w₂ 1) ∧ SatOcc.Chained (w₁ 0) (w₁ 1) s

            The width bound #

            The interpreted structure always satisfies the width promise of 3SAT: every clause piece has at most three literal occurrences (its own literal, the successor's linking variable – unique by succOcc_right_unique – and its own linking variable), and empty-clause copies have none.

            Preservation of satisfiability #

            The chain argument of the reduction, isolated in the form its not-all-equal variant reuses (DescriptiveComplexity.NaeSatToNaeThreeSat): if an assignment of the split gives every output clause a true literal, then, read on the variable copies, it gives every clause of the input a true literal.

            Correctness of the reduction, satisfiability half: an ordered CNF structure is satisfiable iff its width-three split is.

            Correctness of the reduction: an ordered CNF structure is satisfiable iff its width-three split is a yes-instance of 3SAT.

            SAT FO-reduces to 3SAT on ordered structures. The clause-splitting interpretation SatToThreeSat.satToThreeSat, over the ordered expansion of the language of CNF instances, maps a finite CNF structure to a yes-instance of 3SAT iff it is satisfiable. Together with threeSat_fo_reduction_sat, SAT and 3SAT are FO-interreducible.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For