An instance consists of $n$ jobs and $m$ identical parallel machines. Job $j$ has a processing time $p_j \ge 1$, a deadline $d_j \ge p_j$, a weight $w_j$, and a set $M_j$ of eligible machines. Each job is an interval: job $j$, if scheduled, occupies exactly $[d_j - p_j,\, d_j)$, so a schedule chooses only which machine runs a job, never when.

A schedule assigns to every job either an eligible machine or nothing. It is feasible if no machine is assigned two jobs whose intervals overlap. Its weight is the total weight of the jobs it schedules. The optimization problem asks for a feasible schedule of maximum weight; the decision problem asks whether weight $W$ is attainable.

A scheduling instance is handed to a word random access machine as a word of numbers: the number $n$ of jobs, the number $m$ of machines, then the $n$ processing times, the $n$ deadlines, the $n$ weights, then $n+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 $0$ and the last the length of the target array. A decision instance appends the threshold $W$ as a final entry.

A scheduling instance as a binary word, the representation classical complexity measures running time against. A number is written as its binary digits preceded by its length in unary, which makes the encoding self-delimiting; an instance is the number of jobs, the number of machines, the three arrays of processing times, deadlines and weights, and the $n \times m$ eligibility matrix, in that order.

A parameterized problem is a set of admissible input words, a yes-instance predicate on them, and a parameter read off the word. It is fixed-parameter tractable if one word RAM program decides it, on every admissible word $x$ of parameter $k$, within $c\,g(k)\,(|x|+1)$ instructions for a constant $c$ and a function $g$ of the parameter alone.

An fpt-reduction from $P$ to $Q$ is a map on words that sends admissible words to admissible words, preserves and reflects yes-instances, raises the parameter by at most a function of it, and is computed by one word RAM program within the same kind of bound. Fpt-reductions compose, and $Q \in \mathrm{FPT}$ together with $P \le_{\mathrm{fpt}} Q$ gives $P \in \mathrm{FPT}$.

A scheduling problem is NP-hard if every language in NP has a polynomial-time many-one reduction to it, the reduction's output being an instance in the binary encoding.

It is NP-hard on a class $\mathcal C$ of instances if such a reduction exists whose output always lies in $\mathcal C$. When $\mathcal C$ is a slice on which some parameter is bounded by an absolute constant, this is para-NP-hardness for that parameter: it rules out an algorithm running in $f(k)\cdot\mathrm{poly}(n)$ time for every function $f$, unless $\mathrm{P} = \mathrm{NP}$ — a stronger and unconditional-in-$f$ conclusion than W[1]-hardness, which rules out fixed-parameter tractability only under $\mathrm{W}[1] \ne \mathrm{FPT}$.

A polynomial-time many-one reduction from one set of words to another is a map on words, computable by a word RAM program in time polynomial in the bit-size of its input, that preserves and reflects membership. A reduction whose image additionally lies in a given class witnesses hardness on that class.

An instance is a graph on $n$ vertices together with a colouring of its vertices by $k$ colours, in which adjacent vertices always receive different colours. It is a yes-instance if the graph contains a clique with one vertex of each colour — necessarily of size $k$.

Parameterized by the number $k$ of colours, this problem is W[1]-complete. It is the standard starting point for parameterized hardness proofs, because a reduction from it may assume the $k$ vertices of a solution are distinguishable in advance, one per colour.

A $(3,4)$ formula is handed to a word random access machine as a word of numbers: the number of variables, the number of clauses, then three blocks of three numbers per clause, one block per literal, giving the variable it mentions, whether the occurrence is positive, and which of the four occurrences of that variable it is.