The Setting
A recursive split certificate for a job set is a recursive division of that set into regions handled at smaller depths. For dynamic programming on three machines, the completeness question is whether the table at a given depth contains every job set with such a certificate. Let be a finite job set with precedence relation , and let index an assignment of atomic job sets .
A Boolean structural formula over is a signed atomic leaf, or a conjunction or disjunction of two structural formulas.✦ The interpretation of a Boolean structural formula over is a subset of : a positive leaf at denotes , a negative leaf denotes , and conjunction and disjunction denote intersection and union.✦ The leaf count of a Boolean structural formula over is an integer equal to one for a leaf and to the sum of the two constituent counts for either binary operation.✦ A job set is describable with allowance when it satisfies (1). (1)✦
For a nonnegative integer , structural acceptance is a recursive condition on a job set , given by (2). Write for the structural split vertices of , with the left region of a vertex and the right region of a vertex . The relation means that a possibly empty chain of admissible structural split transitions leads from to , with every intervening gap region accepted at depth . (2)✦
A schedule block on is a pair consisting of a nonnegative length and an assigned time for each job .✦ A scheduling table is an ordered list of pairs of finite job sets and schedule blocks. Lookup searches from the beginning and returns the block at the first matching job set, with no result when that set is absent.✦ The key set of a table consists of the job sets whose lookup returns a block.✦
A job triple of is a subset of of cardinality three.✦ Fix a list of candidate job sets and a list of triples. The scheduling layer is a table consisting of the empty job set paired with the empty schedule block.✦ Given , the layer is the table of successful answers obtained by applying the subset solver to every member of , using , the triple list , and the blocks stored in .✦
The Claim
Theorem 1 (Lemma 3.3). Let be a nonnegative integer, and let be structurally accepted at depth . Then (3)✦
In the paper, the result reads: if a feasible job set has a hierarchy with bounded descriptions, the algorithm accepts .
What Is Checked
The assertion (3) is stated over a finite job set with precedence, an assignment of atomic job sets, the candidate family and triple list, and structural acceptance at a nonnegative recursive depth.