WL Distinguishing is XP-hard
Lax119563.XPHardness · concepts/Lax119563/XPHardness.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem. WL Distinguishing, parameterized by the dimension , is -hard under fpt-reductions: every problem in fpt-reduces to it, with a dimension bounded by a computable function of the parameter.
The reduction builds the packed implicit parity system of a run of a decider of the problem and applies the matrix compiler.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax119563.ParameterizedComplexity |
| 2 | import Lax119563.WLProblems |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: WL Distinguishing is XP-hard |
| 7 | type: theorem |
| 8 | --- |
| 9 | **Theorem.** WL Distinguishing, parameterized by the dimension , is |
| 10 | -hard under fpt-reductions: every problem in fpt-reduces to it, |
| 11 | with a dimension bounded by a computable function of the parameter. |
| 12 | |
| 13 | The reduction builds the packed implicit parity system of a run of a decider of the problem |
| 14 | and applies the matrix compiler. |
| 15 | |
| 16 | # Implementation notes |
| 17 | * and fpt-reductions are those of `Lax119563.ParameterizedComplexity`, with |
| 18 | deterministic multitape machines. |
| 19 | * The parameterized problem is `Lax119563.WLProblems.paramWLProblem`. |
| 20 | -/ |
| 21 | |
| 22 | open Lax119563.WLProblems Lax119563.ParameterizedComplexity |
| 23 | |
| 24 | namespace Lax119563.XPHardness |
| 25 | |
| 26 | /-- **XP-hardness.** Every problem in XP fpt-reduces to WL Distinguishing parameterized by the |
| 27 | dimension. -/ |
| 28 | axiom wl_xp_hard : ∀ P ∈ XP, FptReduces P paramWLProblem |
| 29 | |
| 30 | end Lax119563.XPHardness |
| 31 |
Implementation notes
- and fpt-reductions are those of , with deterministic multitape machines.
- The parameterized problem is .
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments