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

WL Distinguishing as a language and as a parameterized problem

Lax119563.WLProblems · concepts/Lax119563/WLProblems.lean · lax-119563

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

    The problem WL Distinguishing asks, given an integer kk and two colored graphs GG and HH, whether kk-WL distinguishes GG and HH. Here kk is part of the input.

    • As a language of bit strings, an instance (k,G,H)(k, G, H) is the binary code of the list of natural numbersk, description of G, description of H,k,\ \text{description of } G,\ \text{description of } H,i.e. the code of kk followed by the binary encoding of the pair (G,H)(G, H), with the number and graph encodings of the binary encodings of graph pairs.
    • As a parameterized problem, it is this language with the parameter kk: the number whose code begins the input string.
    Concept map
    11 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax434930.ExponentialTime
    2import Lax119563.BinaryEncodings
    3import Lax119563.ParameterizedComplexity
    4import Lax119563.WeisfeilerLeman
    5
    6/-!
    7---
    8title: WL Distinguishing as a language and as a parameterized problem
    9type: definition
    10---
    11The problem WL Distinguishing asks, given an integer kk and two colored graphs
    12GG and HH, whether kk-WL distinguishes GG and HH. Here kk is part of the input.
    13
    14* As a **language** of bit strings, an instance (k,G,H)(k, G, H) is the binary code of the list of
    15 natural numbers
    16 k, description of G, description of H,k,\ \text{description of } G,\ \text{description of } H,
    17 i.e. the code of kk followed by the binary encoding of the pair (G,H)(G, H), with the
    18 number and graph encodings of the binary encodings of graph pairs.
    19* As a **parameterized problem**, it is this language with the parameter kk: the number
    20 whose code begins the input string.
    21
    22# Implementation notes
    23* The language is a set of `List Bool`, i.e. a `Lax434930.PolynomialTime.Language`, as used
    24 by the archive's class `EXPTIME` and its many-one reductions, and as in
    25 `Lax119563.DeterministicTime`.
    26* The parameterization must be defined on all bit strings. It reads the leading number code:
    27 pairs of bits `1 d` give the binary digits `d`, least significant first, until the first
    28 pair that does not begin with `1`. On encoded instances, this is `k`.
    29-/
    30
    31open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.BinaryEncodings
    32open Lax119563.ParameterizedComplexity
    33
    34namespace Lax119563.WLProblems
    35
    36/-- The instance `k, description of G, description of H` as a list of natural numbers. -/
    37noncomputable def wlWord (k : ℕ) (G H : ColoredGraph) : List ℕ :=
    38 k :: (graphDescription G ++ graphDescription H)
    39
    40/-- The binary encoding of the instance `(k, G, H)`: the code of `k` followed by the binary
    41encoding of the pair `(G, H)`. -/
    42noncomputable def encodeWLInstance (k : ℕ) (G H : ColoredGraph) : List Bool :=
    43 encodeNats (wlWord k G H)
    44
    45/-- **WL Distinguishing** as a language: the encodings of instances `(k, G, H)` such that
    46`k`-WL distinguishes `G` and `H`. -/
    47def WLDistinguishing : Set (List Bool) :=
    48 {w | ∃ (k : ℕ) (G H : ColoredGraph), w = encodeWLInstance k G H ∧ Distinguishes k G H}
    49
    50/-- The number whose code `encodeNat` begins a bit string. -/
    51def leadingNat : List Bool → ℕ
    52 | true :: d :: rest => (if d then 1 else 0) + 2 * leadingNat rest
    53 | _ => 0
    54
    55/-- **WL Distinguishing** as a parameterized problem, with parameter `k`. -/
    56def paramWLProblem : ParameterizedProblem where
    57 L := WLDistinguishing
    58 κ := leadingNat
    59
    60end Lax119563.WLProblems
    61

    Implementation notes

    • The language is a set of ListBoolList Bool, i.e. a Lax434930.PolynomialTime.LanguageLax434930.PolynomialTime.Language, as used by the archive's class EXPTIMEEXPTIME and its many-one reductions, and as in Lax119563.DeterministicTimeLax119563.DeterministicTime.
    • The parameterization must be defined on all bit strings. It reads the leading number code: pairs of bits 1d1 d give the binary digits dd, least significant first, until the first pair that does not begin with 11. On encoded instances, this is kk.

    Discussion

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

    Loading discussion…