Bounds on the number of machines and jobs
Lax434175.Counts · concepts/Lax434175/Counts.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A count of a kernel assigns a natural number to every instance, such as its number of machines or its number of jobs. The bound field of a count has the values
- at most , for every number : the count is at most , and at least a least number given with the count ( for machines, for jobs);
- constant: no restriction on the instances; the value records that the count is regarded as a constant, as in the notation ;
- unlimited: the count is at least the number of jobs, as in the notation for a machine for every job;
- at most one more than the jobs: the count is at most the number of jobs plus one, as in the notation for the number of machines;
- any: no restriction.
At most is a special case of at most for , of constant and of any; the other values are special cases of any.
In the three-field notation, denotes two machines. Here it is read as at most two machines and at least one, so that the problems with fewer machines are special cases: an instance with one machine is an instance with at most two. An instance without machines belongs to no problem with a bounded number of machines.
Theorem. Over every kernel, for every count and every least number, the bound field is sound.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
-
no assumptions
thm✓Lax434175.Counts
Lean source view on GitHub
| 1 | import Lax434175.Modules |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Bounds on the number of machines and jobs |
| 6 | type: theorem |
| 7 | --- |
| 8 | A count of a kernel assigns a natural number to every instance, such as its |
| 9 | number of machines or its number of jobs. The bound field of a count has the |
| 10 | values |
| 11 | |
| 12 | - at most , for every number : the count is at most , and at least |
| 13 | a least number given with the count ( for machines, for jobs); |
| 14 | - constant: no restriction on the instances; the value records that the |
| 15 | count is regarded as a constant, as in the notation ; |
| 16 | - unlimited: the count is at least the number of jobs, as in the notation |
| 17 | for a machine for every job; |
| 18 | - at most one more than the jobs: the count is at most the number of jobs |
| 19 | plus one, as in the notation for the number of machines; |
| 20 | - any: no restriction. |
| 21 | |
| 22 | At most is a special case of at most for , of constant and |
| 23 | of any; the other values are special cases of any. |
| 24 | |
| 25 | In the three-field notation, denotes two machines. Here it is read as at |
| 26 | most two machines and at least one, so that the problems with fewer machines |
| 27 | are special cases: an instance with one machine is an instance with at most |
| 28 | two. An instance without machines belongs to no problem with a bounded number |
| 29 | of machines. |
| 30 | |
| 31 | **Theorem.** Over every kernel, for every count and every least number, the |
| 32 | bound field is sound. |
| 33 | -/ |
| 34 | |
| 35 | namespace Lax434175.Counts |
| 36 | open Lax434175.Kernels Lax434175.Modules |
| 37 | |
| 38 | inductive Bound |
| 39 | | atMost (k : ℕ) |
| 40 | | constant |
| 41 | | unlimited |
| 42 | | atMostJobsPlusOne |
| 43 | | any |
| 44 | |
| 45 | /-- The numbers admitted by a bound, given the number of jobs. -/ |
| 46 | def Bound.holds : Bound → (jobs count : ℕ) → Prop |
| 47 | | .atMost k, _, n => n ≤ k |
| 48 | | .constant, _, _ => True |
| 49 | | .unlimited, jobs, n => jobs ≤ n |
| 50 | | .atMostJobsPlusOne, jobs, n => n ≤ jobs + 1 |
| 51 | | .any, _, _ => True |
| 52 | |
| 53 | def Bound.le : Bound → Bound → Bool |
| 54 | | _, .any => true |
| 55 | | .atMost k, .atMost l => decide (k ≤ l) |
| 56 | | .atMost _, .constant => true |
| 57 | | .constant, .constant => true |
| 58 | | .unlimited, .unlimited => true |
| 59 | | .atMostJobsPlusOne, .atMostJobsPlusOne => true |
| 60 | | _, _ => false |
| 61 | |
| 62 | /-- The numbers admitted by a bound, given the number of jobs and the least |
| 63 | number that a bound `at most k` admits. -/ |
| 64 | def Bound.admits (least : ℕ) (v : Bound) (jobs n : ℕ) : Prop := |
| 65 | v.holds jobs n ∧ ∀ k, v = .atMost k → least ≤ n |
| 66 | |
| 67 | /-- The bound field of a count; a bound `at most k` admits the counts from |
| 68 | `least` to `k`. -/ |
| 69 | def module (K : Kernel) (count : K.Inst → ℕ) (least : ℕ := 0) : Module K := |
| 70 | Module.ofRestriction Bound (fun v x => v.admits least (K.jobs x) (count x)) Bound.le |
| 71 | |
| 72 | axiom sound (K : Kernel) (count : K.Inst → ℕ) {least : ℕ} : (module K count least).Sound |
| 73 | |
| 74 | end Lax434175.Counts |
| 75 |
Builds on
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments