While this submission is a draft, it cannot be used by other submissions.

Word encoding of a scheduling instance

Lax470956.InstanceEncoding · concepts/Lax470956/InstanceEncoding.lean · lax-470956

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A scheduling instance is handed to a word random access machine as a word of numbers: the number nn of jobs, the number mm of machines, then the nn processing times, the nn deadlines, the nn weights, then n+1n+1 offsets and a target array listing, for each job in turn, the machines eligible to run it. The offsets say where each job's block of eligible machines begins, the first being 00 and the last the length of the target array. A decision instance appends the threshold WW as a final entry.

    Concept map
    2 concepts; 6 descendants hidden
    100%
    Proven claimOpen claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax470956.Scheduling
    2
    3/-!
    4---
    5title: Word encoding of a scheduling instance
    6type: definition
    7---
    8A scheduling instance is handed to a word random access machine as a word of numbers:
    9the number nn of jobs, the number mm of machines, then the nn processing times, the
    10nn deadlines, the nn weights, then n+1n+1 offsets and a target array listing, for each
    11job in turn, the machines eligible to run it. The offsets say where each job's block of
    12eligible machines begins, the first being 00 and the last the length of the target
    13array. A decision instance appends the threshold WW as a final entry.
    14
    15# Formalization notes
    16
    17The eligible sets are in the same compressed sparse row form that presents a graph to a
    18machine elsewhere in the archive, for the same reason: it is the adjacency-array format
    19an algorithm would actually be handed, with nothing precomputed. The blocks are not
    20required to be sorted and repetitions are not forbidden. Leaving those conditions out
    21admits more words and therefore strengthens, rather than weakens, every claim about
    22programs reading the format.
    23
    24Here magnitudes stop being free. The processing times, deadlines
    25and weights are entries of the word, so a claim about a program reading it has to say
    26that they are words — which the fitting conditions of `ParameterizedComplexity` do,
    27once, as an explicit inequality against `2 ^ w`. A size measure that counted only the
    28number of jobs and machines would make the weights of a reduction's output invisible,
    29and a running time stated against it would not be a claim about anything a machine does.
    30
    31Cells are read with `List.getD`, which returns `0` outside the word; the length
    32condition pins the word down completely, so the default is never reached at a position
    33the other conditions constrain. Unlike a graph encoding, the length is not determined by
    34the header alone — the target array is as long as the last offset says — so
    35`length_eq` reads that offset rather than a declared edge count.
    36
    37The threshold is appended last, so that the instance block sits at the same offsets
    38whether or not a threshold follows it, and the split of the word into the two parts is
    39determined by the word rather than chosen.
    40-/
    41
    42namespace Lax470956.InstanceEncoding
    43
    44open Lax470956.Scheduling
    45
    46/-- The number of jobs declared by a word: its first entry. -/
    47def jobCount (x : List ℕ) : ℕ := x.getD 0 0
    48
    49/-- The number of machines declared by a word: its second entry. -/
    50def machineCount (x : List ℕ) : ℕ := x.getD 1 0
    51
    52/-- The processing time of job `j`: the processing times follow the two header
    53entries. -/
    54def proc (x : List ℕ) (j : ℕ) : ℕ := x.getD (2 + j) 0
    55
    56/-- The deadline of job `j`: the deadlines follow the processing times. -/
    57def due (x : List ℕ) (j : ℕ) : ℕ := x.getD (2 + jobCount x + j) 0
    58
    59/-- The weight of job `j`: the weights follow the deadlines. -/
    60def wt (x : List ℕ) (j : ℕ) : ℕ := x.getD (2 + 2 * jobCount x + j) 0
    61
    62/-- The `i`-th offset: the `n+1` offsets follow the weights. -/
    63def offset (x : List ℕ) (i : ℕ) : ℕ := x.getD (2 + 3 * jobCount x + i) 0
    64
    65/-- The `t`-th entry of the target array, which follows the offsets. -/
    66def target (x : List ℕ) (t : ℕ) : ℕ := x.getD (3 + 4 * jobCount x + t) 0
    67
    68/-- The word `x` encodes the instance `I`. -/
    69structure EncodesInstance (x : List ℕ) (I : Instance) : Prop where
    70 /-- The word declares `I`'s jobs. -/
    71 jobCount_eq : jobCount x = I.jobs
    72 /-- The word declares `I`'s machines. -/
    73 machineCount_eq : machineCount x = I.machines
    74 /-- The word consists of the two header entries, the three arrays of one number per
    75 job, the `n+1` offsets, and a target array as long as the last offset says. -/
    76 length_eq : x.length = 3 + 4 * I.jobs + offset x I.jobs
    77 /-- The processing times are `I`'s. -/
    78 proc_eq : ∀ j : Fin I.jobs, proc x j = I.p j
    79 /-- The deadlines are `I`'s. -/
    80 due_eq : ∀ j : Fin I.jobs, due x j = I.d j
    81 /-- The weights are `I`'s. -/
    82 wt_eq : ∀ j : Fin I.jobs, wt x j = I.w j
    83 /-- The block of the first job begins at the start of the target array. -/
    84 offset_zero : offset x 0 = 0
    85 /-- The offsets are nondecreasing, so they cut the target array into one block per
    86 job. -/
    87 offset_mono : ∀ j < I.jobs, offset x j ≤ offset x (j + 1)
    88 /-- Every entry of the target array is a machine. -/
    89 target_lt : ∀ t < offset x I.jobs, target x t < I.machines
    90 /-- The block of a job lists exactly its eligible machines. -/
    91 eligible_iff : ∀ (j : Fin I.jobs) (i : Fin I.machines),
    92 i ∈ I.eligible j ↔ ∃ t, offset x j ≤ t ∧ t < offset x (j + 1) ∧ target x t = i
    93
    94/-- The word `x` presents the instance `I` together with the threshold `W`: an instance
    95block followed by the single entry `W`. -/
    96def EncodesDecisionInstance (x : List ℕ) (I : Instance) (W : ℕ) : Prop :=
    97 ∃ y, x = y ++ [W] ∧ EncodesInstance y I
    98
    99/-- The words that encode a decision instance. -/
    100def DecisionInstances : Set (List ℕ) :=
    101 {x | ∃ I W, EncodesDecisionInstance x I W}
    102
    103/-- The words that encode an instance, with no threshold. -/
    104def Instances : Set (List ℕ) := {x | ∃ I, EncodesInstance x I}
    105
    106end Lax470956.InstanceEncoding
    107
    Formalization notes

    The eligible sets are in the same compressed sparse row form that presents a graph to a machine elsewhere in the archive, for the same reason: it is the adjacency-array format an algorithm would actually be handed, with nothing precomputed. The blocks are not required to be sorted and repetitions are not forbidden. Leaving those conditions out admits more words and therefore strengthens, rather than weakens, every claim about programs reading the format.

    Here magnitudes stop being free. The processing times, deadlines and weights are entries of the word, so a claim about a program reading it has to say that they are words — which the fitting conditions of ParameterizedComplexityParameterizedComplexity do, once, as an explicit inequality against 2w2 ^ w. A size measure that counted only the number of jobs and machines would make the weights of a reduction's output invisible, and a running time stated against it would not be a claim about anything a machine does.

    Cells are read with List.getDList.getD, which returns 00 outside the word; the length condition pins the word down completely, so the default is never reached at a position the other conditions constrain. Unlike a graph encoding, the length is not determined by the header alone — the target array is as long as the last offset says — so lengtheqlength_eq reads that offset rather than a declared edge count.

    The threshold is appended last, so that the instance block sits at the same offsets whether or not a threshold follows it, and the split of the word into the two parts is determined by the word rather than chosen.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…