Results between parameters of one problem
Lax434175.Domination · concepts/Lax434175/Domination.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A parameter of a problem is dominated by a parameter if for a function and every instance and threshold . Then the identity on words is an fpt-reduction from the problem with to the problem with when is computable, and the words with are among those with .
Theorem. If is dominated by , then para-NP-hardness and W[t]-hardness for hold for , and membership in XP and fixed-parameter tractability for hold for ( computable for the last two).
Two dominations of the zoo's parameters: a summand is dominated by a sum, and on the operations family the number of distinct processing times is at most (the values lie in ).
Theorem. These dominations hold.
Concept map
Evidence
This concept declares 7 statements. Each proof establishes one of them relative to its assumptions.
1 inPFixed_of_dominated proven
2 isFPT_of_dominated proven
3 left_tplus proven
4 ops_numP_pmax proven
5 paraNPHard_of_dominated proven
6 right_tplus proven
7 wHard_of_dominated proven
Lean source view on GitHub
| 1 | import Lax434175.ResultParameters |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Results between parameters of one problem |
| 6 | type: theorem |
| 7 | --- |
| 8 | A parameter of a problem is *dominated* by a parameter if |
| 9 | for a function and every instance and |
| 10 | threshold . Then the identity on words is an fpt-reduction from the problem |
| 11 | with to the problem with when is computable, and the |
| 12 | words with are among those with . |
| 13 | |
| 14 | **Theorem.** If is dominated by , then para-NP-hardness and |
| 15 | W[t]-hardness for hold for , and membership in XP and |
| 16 | fixed-parameter tractability for hold for ( computable for |
| 17 | the last two). |
| 18 | |
| 19 | Two dominations of the zoo's parameters: a summand is dominated by a sum, and |
| 20 | on the operations family the number of distinct processing times is at |
| 21 | most (the values lie in ). |
| 22 | |
| 23 | **Theorem.** These dominations hold. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax434175.Domination |
| 27 | open Lax434175 Lax434175.Problems Lax434175.Results Lax434175.ResultParameters |
| 28 | open Lax496464.WH_A2_FptReductions |
| 29 | |
| 30 | variable {P : Problem} |
| 31 | |
| 32 | /-- `κ'` is bounded by `g` of `κ` on every instance and threshold. -/ |
| 33 | def Dominated (κ' κ : TParameter P) (g : ℕ → ℕ) : Prop := ∀ x D, κ' x D ≤ g (κ x D) |
| 34 | |
| 35 | axiom paraNPHard_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ} |
| 36 | (h : Dominated κ' κ g) : ParaNPHard R κ → ParaNPHard R κ' |
| 37 | |
| 38 | axiom wHard_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ} (t : ℕ) |
| 39 | (hg : Computable g) (h : Dominated κ' κ g) : WHard R t κ → WHard R t κ' |
| 40 | |
| 41 | axiom inPFixed_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ} |
| 42 | (h : Dominated κ' κ g) : InPFixed R κ' → InPFixed R κ |
| 43 | |
| 44 | axiom isFPT_of_dominated {R : PReading P} {κ κ' : TParameter P} {g : ℕ → ℕ} |
| 45 | (hg : Computable g) (h : Dominated κ' κ g) (hp : IsParameterized (parameterized R κ)) : |
| 46 | IsFPT R κ' → IsFPT R κ |
| 47 | |
| 48 | axiom left_tplus (κ κ' : TParameter P) : Dominated κ (tplus κ κ') id |
| 49 | |
| 50 | axiom right_tplus (κ κ' : TParameter P) : Dominated κ' (tplus κ κ') id |
| 51 | |
| 52 | axiom ops_numP_pmax (s : Assembly.Spec OperationsFamily.family) : |
| 53 | Dominated (lift (Ops.numP s)) (lift (Ops.pmax s)) (· + 1) |
| 54 | |
| 55 | end Lax434175.Domination |
| 56 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments