WL Distinguishing as a language and as a parameterized problem
Lax119563.WLProblems · concepts/Lax119563/WLProblems.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The problem WL Distinguishing asks, given an integer and two colored graphs and , whether -WL distinguishes and . Here is part of the input.
- As a language of bit strings, an instance is the binary code of the list of natural numbersi.e. the code of followed by the binary encoding of the pair , with the number and graph encodings of the binary encodings of graph pairs.
- As a parameterized problem, it is this language with the parameter : the number whose code begins the input string.
Concept map
Lean source view on GitHub
| 1 | import Lax434930.ExponentialTime |
| 2 | import Lax119563.BinaryEncodings |
| 3 | import Lax119563.ParameterizedComplexity |
| 4 | import Lax119563.WeisfeilerLeman |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: WL Distinguishing as a language and as a parameterized problem |
| 9 | type: definition |
| 10 | --- |
| 11 | The problem WL Distinguishing asks, given an integer and two colored graphs |
| 12 | and , whether -WL distinguishes and . Here is part of the input. |
| 13 | |
| 14 | * As a **language** of bit strings, an instance is the binary code of the list of |
| 15 | natural numbers |
| 16 | |
| 17 | i.e. the code of followed by the binary encoding of the pair , 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 : 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 | |
| 31 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.BinaryEncodings |
| 32 | open Lax119563.ParameterizedComplexity |
| 33 | |
| 34 | namespace Lax119563.WLProblems |
| 35 | |
| 36 | /-- The instance `k, description of G, description of H` as a list of natural numbers. -/ |
| 37 | noncomputable 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 |
| 41 | encoding of the pair `(G, H)`. -/ |
| 42 | noncomputable 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`. -/ |
| 47 | def 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. -/ |
| 51 | def 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`. -/ |
| 56 | def paramWLProblem : ParameterizedProblem where |
| 57 | L := WLDistinguishing |
| 58 | κ := leadingNat |
| 59 | |
| 60 | end Lax119563.WLProblems |
| 61 |
Implementation notes
- The language is a set of , i.e. a , as used by the archive's class and its many-one reductions, and as in .
- The parameterization must be defined on all bit strings. It reads the leading number code: pairs of bits give the binary digits , least significant first, until the first pair that does not begin with . On encoded instances, this is .
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments