WL Distinguishing is EXPTIME-hard
Lax119563.EXPTIMEHardness · concepts/Lax119563/EXPTIMEHardness.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem. WL Distinguishing is -hard under polynomial-time many-one reductions: every language decided by a deterministic machine in time reduces in polynomial time to WL Distinguishing.
The reduction builds the packed implicit parity system of a run of the machine and applies the matrix compiler; the dimension grows with the input.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax429075.Reductions |
| 2 | import Lax119563.WLProblems |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: WL Distinguishing is EXPTIME-hard |
| 7 | type: theorem |
| 8 | --- |
| 9 | **Theorem.** WL Distinguishing is -hard under polynomial-time |
| 10 | many-one reductions: every language decided by a deterministic machine in time |
| 11 | reduces in polynomial time to WL Distinguishing. |
| 12 | |
| 13 | The reduction builds the packed implicit parity system of a run of the machine and applies |
| 14 | the matrix compiler; the dimension grows with the input. |
| 15 | |
| 16 | # Implementation notes |
| 17 | * is the archive's `Lax434930.ExponentialTime.EXPTIME` (single-tape |
| 18 | machines), and polynomial-time many-one reductions are `Lax429075.Reductions.ManyOne` |
| 19 | (multi-stack machines in polynomial time). |
| 20 | * The language is `Lax119563.WLProblems.WLDistinguishing`, with the dimension part of the |
| 21 | input. |
| 22 | -/ |
| 23 | |
| 24 | open Lax434930.ExponentialTime Lax429075.Reductions |
| 25 | open Lax119563.WLProblems |
| 26 | |
| 27 | namespace Lax119563.EXPTIMEHardness |
| 28 | |
| 29 | /-- **EXPTIME-hardness.** Every language in EXPTIME reduces in polynomial time to WL |
| 30 | Distinguishing. -/ |
| 31 | axiom wl_exptime_hard : ∀ L ∈ EXPTIME, ManyOne L WLDistinguishing |
| 32 | |
| 33 | end Lax119563.EXPTIMEHardness |
| 34 |
Implementation notes
- is the archive's (single-tape machines), and polynomial-time many-one reductions are (multi-stack machines in polynomial time).
- The language is , with the dimension part of the input.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments