The Complexity of Value Optimization in Sporadic Task Systems

Introduction

Choosing a valuable task set and deciding whether a fixed task set is feasible are often treated as separate questions. We study the combined problem: given a finite collection of independent sporadic tasks on one preemptive processor, each with an associated value, can one select a subset whose total value reaches a prescribed target and whose jobs all meet their deadlines under every legal release sequence? The selection is made offline, with the entire collection available. Once a task is selected, every job of that task must retain its hard-deadline guarantee. We show that this task-selection problem, which we call the Value-based Task Selection (VTS) problem, has the existential-universal structure of the second level of the polynomial hierarchy.

The central result is that VTS is $\Sigma^{P}_{2}$-complete for both constrained and arbitrary deadlines, even when all numerical parameters are encoded in unary. Optional selector tasks encode an existential choice, while demand windows expose possible counterexamples to that choice. For a well-formed selection, the construction creates more required execution than available processor time in a window exactly when the encoded choice has a logical counterexample. The remainder of this section develops this interpretation before stating the contributions and organization of the paper.

Motivation

Real-time systems may contain more useful functionality than their available processing capacity can support. A concrete design-time setting is the configuration of an embedded platform whose recurrent tasks implement optional monitoring, diagnostic, or quality-enhancement functions. Enabling a feature selects its entire sporadic task: every job must meet its hard deadline under every legal release sequence. Disabling the feature removes the complete recurrent workload. Selecting more functionality increases total value, but the resulting workload must still meet every hard deadline.

Utility-driven task selection also appears in cloud computing. Li and Wu [19] select periodic tasks and their parallelization options to maximize total utility on multiple processing units, under implicit deadlines. That model differs from our sequential sporadic tasks on one processor, but it provides a concrete example of choosing which recurrent workloads to retain under limited processing capacity.

For implicit-deadline tasks on one preemptive processor, each selected task consumes a single utilization share, giving the scalar-capacity structure of 0-1 knapsack. With constrained deadlines, the same selected set must instead satisfy a family of processor-demand inequalities, one for each relevant interval length. The standard single-capacity knapsack formulation therefore does not directly supply algorithms or approximation guarantees for this setting.

This task-selection problem also connects to multiple-implementation selection (MIS), where exactly one implementation is chosen per functionality. If MIS permits a disabled option with zero execution and zero value, each task becomes a two-option choice: select it or disable its functionality. Section 2 gives this embedding and the resulting completeness classification under the same scheduling assumptions.

Problem Overview

Following the sporadic task model introduced by Mok [22], the input is an indexed multiset of tasks

where $C_i$, $D_i$, and $T_i$ are execution time, relative deadline, and minimum inter-arrival separation, and $V_i$ is the value of selecting $\tau_i$. We consider independent tasks on one preemptive unit-speed processor. Earliest deadline first (EDF) is optimal under these assumptions. The formal model appears in Section 3.

We study the threshold decision form because completeness is defined for decision problems: the VTS problem determines whether the maximum feasible value is at least $K$. For a selected indexed submultiset $A$, write

In the implicit-deadline case $D_i = T_i$, EDF feasibility is equivalent to

Therefore tasks act as knapsack items, their values are $V_i$, and their sizes are utilization shares $C_i/T_i$. This is the classical 0-1 knapsack structure, for which exact and approximation algorithms are well studied [8, 15] (Kellерer et al. 2004).

Constrained deadlines replace this single capacity constraint with interval-dependent demand constraints. The demand bound function (DBF), denoted $\operatorname{dbf}(A,\ell)$, is the maximum execution demand of jobs of $A$ that can both arrive and have their deadlines within an interval of length $\ell$. Feasibility requires $\operatorname{dbf}(A,\ell) \le\ell$ for every $\ell> 0$ (e.g., see Baruah et al. [4]); Section 3 gives the formula and exact criterion.

Why the Problem Has a Sigma-2-P Shape

Throughout this explanation, a proposed solution or counterexample is called short if its encoding length is bounded by a polynomial in the input size. The predicate $R$ is computable in polynomial time. The polynomial hierarchy extends NP and coNP through successive levels with a fixed number of alternations between existential and universal choices [27, 28]. For an NP problem, an instance $I$’s membership is confirmed by exhibiting one short proposed solution $w$ and checking it in polynomial time: $\exists w : R(I,w) = 1$. For a coNP problem, membership is confirmed only if every short proposed counterexample $w$ fails to break it: $\forall w : R(I,w) = 1$. The second existential level, $\Sigma^{P}_{2}$, combines these two ideas:

In plain terms, there is a short candidate solution that remains valid under every short challenge. For VTS, after choosing tasks whose value reaches the target, one question remains: can this set meet every deadline? Imagine being able to hand the set to a checker and get a correct yes-or-no answer. Complexity theory calls this assumed checker an oracle. We could ask “Is the set feasible?” or instead ask “Is there a demand window that overloads the processor?” A yes to one means a no to the other. The feasibility question is in coNP; the overload question is in NP. Either answer therefore lets us judge our chosen set, giving the two equivalent descriptions

Ekberg and Baruah [12] discuss these views and their relevance to real-time scheduling. Figure 1 illustrates the levels of the polynomial hierarchy and how each one builds on the levels below it.

The order of the choices distinguishes the two branches: $\Sigma^{P}_{2}$ chooses first and then tests every response; $\Pi^{P}_{2}$ reverses that order. VTS follows the first pattern.

The VTS decision problem has the form:

The selected set $A$ is the existential choice. Once $A$ is fixed, one interval satisfying $\operatorname{dbf}(A,\ell) > \ell$ is a counterexample to its feasibility. The display describes the scheduling condition; Section 4 establishes the polynomial-length counterexample bound needed for the complexity classification. A $\Sigma^{P}_{2}$-completeness result is therefore stronger than separate NP- and coNP-hardness results. Unless the polynomial hierarchy collapses, the problem lies in neither NP nor coNP.

Contributions

• We formalize the threshold decision form of Value-based Task Selection for sporadic tasks on one preemptive processor: every selected task executes in full, and the selected set must reach a prescribed value target.

• We prove that VTS is $\Sigma^{P}_{2}$-complete for both constrained and arbitrary deadlines. The constrained-deadline hardness construction uses demand windows indexed via the Chinese Remainder Theorem (CRT) to represent universal responses and a polynomial-weight local selector lock to enforce one existential truth choice per variable.

• We prove that the construction produces polynomially many tasks and polynomially bounded numerical parameters. As a result, completeness also holds when all numerical parameters are encoded in unary.

Organization

§ 2 reviews related work, and § 3 defines the model and decision problem. Section 4 proves membership in $\Sigma^{P}_{2}$. § 5 introduces the quantified source problem, summarizes the complete construction, and states the reduction invariant. § 6 and § 7 develop the demand gadgets and selector lock. § 8 and § 9 give the detailed construction and correctness proof, and § 10 proves the task-count and numerical-parameter bounds. § 11 states the completeness theorem. § 12 and § 13 discuss its implications and conclude.

Related Work

Four strands of prior work provide the closest context for this problem: real-time admission control, optional or imprecise execution, exact uniprocessor feasibility analysis, and polynomial-hierarchy classifications in real-time scheduling. They differ in what is selected, when the selection is made, or which scheduling platform is studied.

Admission Control and Value-Aware Scheduling

Classical real-time admission control decides whether newly arriving work can be accepted without invalidating guarantees already made to admitted work [7] Andersson and Ekelin, 2005). The problem studied here instead receives the entire task collection at design time and selects a feasible subset whose fixed task values reach a target.

Value-based overload scheduling treats completed work as an optimization objective. Burns et al. [5] survey the role of value in flexible real-time scheduling, while Koren and Shasha [18] study online utility-maximizing admission under overload. More recent work studies value-aware scheduling for transportation applications and response-time-dependent utility accrual [29, 6]. These models provide related utility objectives; they do not establish the complexity of the offline whole-task selection problem studied here.

Knapsack formulations also arise in other real-time resource decisions. Mejia-Alvarez et al. [21] choose among discrete processor speeds to improve energy savings under timing constraints. Goossens and Richard [16] use a knapsack subproblem to bound a mode-transition delay in partitioned multimode scheduling. The objectives and scheduling models differ from ours; these examples illustrate the use of scalar-capacity selection subproblems in real-time analysis.

Multiple-choice knapsack selects exactly one alternative from each group [26]. A related multiple-implementation selection (MIS) model chooses exactly one implementation per functionality. For example, alternative classifiers for the same classification task may trade execution demand against utility. For MIS models permitting an explicit disabled implementation, task selection is the special case with two alternatives per functionality: the given task, or a disabled option with zero execution and zero value. The latter is an option of the extended model, not a task in our positive-parameter domain. For explicitly listed alternatives under the same scheduling assumptions, this MIS threshold decision problem is $\Sigma_{2}^{P}$-complete for both constrained and arbitrary deadlines. Hardness follows from the two-option embedding. For membership, guess exactly one implementation per functionality, check the total value, and apply the feasibility check to the selected implementations (see Theorem 2).

Optional and Imprecise Execution

Imprecise-computation and reward-based models divide work into mandatory and optional portions, allowing result quality to improve as optional execution is completed [20, 25, 3]. These models optimize how much optional service to execute after preserving mandatory timing guarantees. In contrast, our decision is made at task granularity: a selected sporadic task executes in full, and all of its jobs must meet hard deadlines.

Feasibility and Complexity of Uniprocessor Scheduling

For preemptive uniprocessor scheduling of constrained-deadline sporadic tasks, processor demand gives a necessary and sufficient feasibility condition [4]. The complexity of evaluating such conditions was clarified in stages. Eisenbrand and Rothvoß proved weak coNP-hardness for EDF schedulability of synchronous periodic task systems, and Ekberg and Yi later established strong coNP-completeness for constrained-deadline sporadic feasibility [11, 13]. Related difficulty also appears under static-priority scheduling: exact response-time computation is NP-hard [10].

Our reduction builds on the modular structure used in the constrained-deadline feasibility result. CRT-based constructions identify demand windows whose residue patterns represent Boolean assignments; the constructed deadline offsets turn matching patterns into controlled processor-demand spikes.

Polynomial-Hierarchy Results in Real-Time Scheduling

Ekberg and Baruah [12] classify a broad family of partitioned multiprocessor schedulability problems rather than treating them uniformly as NP-hard. For asynchronous periodic task systems scheduled by EDF, they prove that the constrained- and arbitrary-deadline partitioning problems are $\Sigma^{P}_{2}$-complete, for both a constant and an arbitrary number of processors. For fixed-priority scheduling, several corresponding problems are $\Sigma^{P}_{2}$-hard but have only a $\Sigma^{P}_{3}$ upper bound; exact classification therefore remains open in those cases. They also identify fixed-priority implicit-deadline cases whose classification depends on whether the priority order is specified.

Agrawal et al. [1] relate exact, pseudo-polynomial, and approximation-based notions of tractability in real-time schedulability analysis. They also analyze a memory-constrained task-selection problem to illustrate limits of approximation schemes. That selection model and objective differ from the hard-deadline value-threshold problem studied here.

Our result exhibits the same higher-level quantifier structure without a partitioning decision or multiple processors. Here the existential choice is which tasks to select, and the universal condition requires the resulting single-processor task set to satisfy every processor-demand constraint.

Model and Problem Definition

This section fixes the model before any complexity argument begins. It defines sporadic tasks, deadline restrictions, and the assumptions under which EDF is optimal, introduces the demand bound function and its exact feasibility criterion, and then defines the value-threshold decision problem.

Task Model

Demand Bound Function

For a selected indexed submultiset $A$, define its demand bound function (DBF) by

Throughout the paper, $A$ denotes a selected task set. For each task, the floor term counts the largest number of jobs that can both arrive and have their deadlines within a window of length $\ell$. Multiplying that count by $C_i$ gives the corresponding execution demand. Summing over the selected tasks therefore measures the maximum processor demand that must fit inside the window.

The utilization of $A$ is

Every term of $\operatorname{dbf}(A,\ell)$ and $U(A)$ is nonnegative, so demand and utilization are monotone in the selected set. In particular, removing tasks from a feasible set preserves feasibility. Therefore additional tasks can increase total value while making the selected set infeasible.

Feasibility Criterion

The DBF is a right-continuous step function of the interval length $\ell$. Its possible discontinuities occur at $D_i + kT_i$, for $\tau_i \in A$ and integers $k \ge0$. These are deadlines in a synchronous minimum-separation release pattern; an arbitrary sporadic release sequence can have different absolute deadlines.

VTS Decision Problem

The constrained-deadline restriction additionally requires $D_i \le T_i$ for every input task.

The DBF condition already implies $U(A) \le1$, since

A selection $A$ meets the value target when $V(A) \ge K$. This value condition alone does not imply that $A$ is feasible.

With the decision problem fixed, the next section proves the upper bound needed for the completeness result.

Membership in $\Sigma_2^P$

The upper-bound argument separates the same two roles used in the hardness construction. A selection vector supplies the existential choice. Once that choice is fixed, one polynomial-length demand window can verify infeasibility, so feasibility is a coNP condition.

Proof. Consider a candidate selection vector that specifies a selected indexed submultiset $A$. Its value $V(A)$ is computable in polynomial time. The remaining question is whether this fixed task set is feasible. The following argument verifies infeasibility in NP for any sporadic task system, using Theorem 1. If $U(A)>1$, infeasibility is direct. The empty selection is trivially feasible. For nonempty $A$ with $U(A)\le1$, let

For every $\ell>P(A)+D_{\max}(A)$, increasing the window length by one hyper-period $P(A)$ adds exactly $P(A)C_i/T_i$ demand from each task $\tau_i\in A$. Therefore,

Because $U(A)\le1$, a violation at $\ell$ implies a violation at $\ell-P(A)$. Repeating this shift shows that, if $A$ is infeasible, some violating window satisfies $\ell\le P(A)+D_{\max}(A)$. By Lemma 1, it may be chosen at a DBF discontinuity. Although $P(A)$ can be exponentially large, its binary representation has at most $1+\sum_{\tau_i\in A}\lceil\log_2 T_i\rceil$ bits. Since $D_{\max}(A)$ is an input parameter, every $\ell\le P(A)+D_{\max}(A)$ also has polynomial binary length. Given this binary-encoded $\ell$, checking $\operatorname{dbf}(A,\ell)>\ell$ takes polynomial time. Therefore infeasibility has an NP verification, and feasibility is in coNP. Once a selection $A$ is chosen, the combined condition that $V(A)\ge K$ and $A$ is feasible is therefore coNP-decidable. The VTS decision problem asks whether such a selection exists, placing it in $\mathrm{NP}^{\mathrm{coNP}}=\Sigma^{\mathrm{P}}_2$.

Reduction Overview

We now introduce the quantified source problem and summarize the construction and its proof obligations.

Source Problem and Reduction Idea

We reduce from the standard $\Sigma^{\mathrm{P}}_2$-complete $\exists\forall$-3DNF problem [27, 28, 24]. Its instances have the form

Here $X=\{x_1,\ldots,x_n\}$, $Y=\{y_1,\ldots,y_u\}$, and $\varphi$ is a three-literal disjunctive-normal-form (3-DNF) formula with exactly three literals over distinct variables in each term. The question is whether some assignment $\alpha$ to $X$ makes $\varphi(\alpha,\beta)$ true for every assignment $\beta$ to $Y$. Under the quantifier interpretation, the existential player commits to $\alpha$ first. That choice must survive every response $\beta$ of the universal player. Appendix A justifies this normal form.

Fix an existential assignment $\alpha$. To show that $\alpha$ is not winning, it is enough to find one universal assignment $\beta$ for which $\varphi(\alpha,\beta)$ is false. We therefore work with its negation, a three-literal conjunctive-normal-form (3-CNF) formula:

We write $C_k$ for a clause, reserving $C_i$ for task execution time. Therefore $F(\alpha,\beta)$ is true exactly when $\beta$ is a counterexample to $\alpha$, and $\alpha$ is winning exactly when no $\beta$ satisfies $F(\alpha,\beta)$. The reduction uses three representations of the counterexample condition: Boolean patterns, modular tests, and task demands. First, we identify the variable-consistency and clause-satisfaction patterns to recognize. Second, we convert these clause-satisfaction patterns into a number-theoretic representation as sets of congruences, which describe recurring sets of integers. In this number-theoretic construction, truth assignments to boolean variables are represented by integer “coordinates” and the set of congruences enforce a consistent assignment of truth values in these clause-satisfaction patterns. Third, using the number-theoretic representation of the Boolean formula $F$, we construct sporadic tasks whose combined demand encodes the congruences derived in the previous step. For each existential assignment $\alpha$, the construction provides a corresponding task selection for which a deadline miss is possible exactly when some assignment $\beta$ satisfies $F(\alpha,\beta)$. The following paragraphs explain these translations.

We construct the entire task collection from $F$ before any optional selection is made. The modular tests are imposed on a nonnegative integer demand-window index $x$. Each coordinate has an assigned prime, and its value at $x$ is the residue of $x$ modulo that prime. Different coordinates use different primes. Boolean tests use residues $0$ and $p-1$ modulo a coordinate’s prime $p$. A pattern specifies the coordinate residues required for one local test. The Chinese Remainder Theorem (CRT) combines these requirements into one congruence $x \equiv a \pmod{b}$, where $b$ is the product of the pattern’s primes.

For example, the coordinate requirements $x \equiv2 \pmod{3}$ and $x \equiv0 \pmod{5}$ combine into $x \equiv5 \pmod{15}$. This illustrates one pattern; the construction applies the same translation to its clause and consistency tests.

A full gadget $G(a,b,w)$ converts the congruence and a weight $w$ into $b$ ordinary sporadic tasks. Their execution times, deadlines, and periods are chosen so that, at designated test windows, their combined demand equals a baseline contribution plus $w$ when the index matches the congruence, and equals the baseline otherwise. Thus the pattern specifies a test, CRT supplies its arithmetic form, and the gadget supplies the tasks that implement it. All gadgets inspect the same index $x$, so matching patterns agree on every shared coordinate.

The optional selectors are individual tasks. Choosing one of two selectors per existential variable fixes $\alpha$. Each clause of $F$ has a pattern for each satisfying assignment to its three variables, while additional patterns provide validity and consistency tests. CRT also ensures that one index can realize one prescribed residue for each coordinate simultaneously. Arbitrary indices need not represent Boolean assignments; the validity, consistency, and clause tests together prevent these indices from creating false counterexamples.

The value target forces every task of every full gadget into the selected set. Utilization and demand constraints then enforce exactly one selector per existential variable. A selection with this structure is called well formed. For such a selection encoding $\alpha$, an overloaded window exists exactly when some universal assignment $\beta$ satisfies $F(\alpha,\beta)$. This describes how the negated matrix is used inside the reduction; the source problem is still $\exists X\forall Y\ \varphi(X,Y)$, with its 3-DNF matrix. We assume $n \ge1$, adding an unused existential variable if necessary, which leaves the answer unchanged.

Figure 2 gives the complete reduction at the level of roles rather than formulas. Later sections define the boxes in the middle of the figure; the correctness proof shows that their composition has the behavior stated on the right.

Construction at a Glance

Before developing the gadgets, we summarize the complete output instance. The detailed task parameters appear in Sections 6–8. A full gadget $G(a,b,w)$ expands into $b$ tasks and recognizes one residue pattern. The selector $H(p,w)$ is a single optional task with a weight-$w$ demand spike at the designated test windows when $x \equiv p-1 \pmod{p}$.

Each existential variable $x_i$ has two coordinates, $t_i$ and $f_i$, with distinct primes. Each universal variable $y_j$ has one coordinate with its own prime. An index is exact for $x_i$ when both of its coordinate residues are Boolean. For these exact tests, write 1 for a coordinate’s maximum residue $p-1$ and 0 for residue zero. In the order $(t_i,f_i)$, the pairs 10 and 01 encode true and false; 11 and 00 are the both-match and neither-match consistency tests. These pairs describe the window index’s residues, not which tasks were selected.

The inventory uses three demand parameters: $W_0$ is the anchor weight, $q$ is the selector weight, and $S$ is the local spike budget for one existential variable. These parameters control execution demand; task values, which determine whether the selection reaches its target, are assigned separately below.

The output has the following five task families:

1. To supply a common demand offset, one always-matching anchor $G(0,1,W_0)$.

2. To test consistency of the existential choices, four full helpers per $x_i$, for exact states 10, 01, 11, 00, with weights 1, 1, 1, $S$, respectively.

3. To recognize Boolean universal values, two unit-weight full gadgets per $y_j$, for residues 0 and $p_{y_j}-1$.

4. To recognize clause satisfaction, seven unit-weight full gadgets per clause $C_k$, one for each satisfying assignment to its three distinct variables.

5. To choose the existential assignment, two optional selectors per $x_i$: $\tau_i^t = H(p_{t_i},q)$ and $\tau_i^f = H(p_{f_i},q)$.

Let $\mathcal{P}$ be the weighted multiset of patterns in families 2–4. Each $\rho\in\mathcal{P}$ specifies a congruence $a_\rho\pmod{b_\rho}$ and a weight $w_\rho$. The detailed residue requirements appear in Section 8. Let $p_{\max}$ be the largest coordinate prime. The constants have the following roles:

• The selector weight $q$ and local spike budget $S$ are

At most one satisfying pattern matches per clause, so the entire clause layer contributes at most $m$ units of extra demand above its baseline. Choosing $q > m$ makes a duplicate selector’s penalty larger than that possible contribution. A matching selector together with a matching unit helper fills the budget $S.

• The total non-anchor mandatory weight and the anchor weight are

Here $B_{\mathrm{mand}}$ sums gadget weights, not individual tasks. The anchor supplies a fixed demand offset and helps ensure that the resulting tasks satisfy the constrained-deadline requirements.

• The common timing scale is

This choice makes the utilization of all mandatory tasks and exactly $n$ selected selectors equal to one.

• The forbidden extra-demand threshold is

The terms correspond to the anchor, the $n$ local budgets, the $u$ universal-variable tests, and the $m$ clause tests. § 6 explains how the test-window lengths make this threshold exceed the capacity remaining beyond the baseline budget.

Using indexed multiset union, the complete task collection is

Let $M = |\Gamma_{\mathrm{mand}}|$. Each task in $\Gamma_{\mathrm{mand}}$ receives value $V_0 = 2n + 1$, each optional selector receives value 1, and the target is $K = MV_0 + n$. These values force every task in $\Gamma_{\mathrm{mand}}$ into any selection meeting the target; the model itself has no mandatory-task constraint.

We call a selection well formed if it contains every task in $\Gamma_{\mathrm{mand}}$ and exactly one of $\tau_i^t,\tau_i^f$ for each $x_i$. Such a selection has value $K$ and utilization one. The proof must establish that every feasible selection meeting the value target is well formed and that a well-formed selection is feasible exactly when its encoded existential assignment is winning.

Reduction Roadmap

The demand gadgets of § 6 and the local selector tests of § 7 support four proof obligations:

1. Force the required tasks and selector count. The values chosen in § 8 force every mandatory task and at least $n$ selectors into a selection meeting the target. The utilization bound permits at most $n$. § 9 therefore obtains exactly $n$ selected selectors in total.

2. Distribute the selectors one per variable. The local tests of § 7 expose a duplicated choice without allowing a missing choice elsewhere to offset its extra demand. § 9 uses CRT to realize these tests at one common index and obtain an overloaded window. Therefore every feasible selection meeting the target is well formed and defines one assignment $\alpha$.

3. Relate feasibility to the source formula. For a well-formed selection, § 9 proves that a winning $\alpha$ satisfies every demand constraint. Conversely, any universal response $\beta$ satisfying $F(\alpha,\beta)$ has a compatible index producing an overloaded window.

4. Verify the reduction’s size and task parameters. Section 10 proves that the construction takes polynomial time, produces polynomially many tasks with polynomially bounded numerical parameters, and satisfies $C_i \le D_i \le T_i$ for every task.

The logical correspondence is summarized by the invariant:

In this construction, an $X$-helper tests two coordinates, a $Y$-validity pattern tests one, and a clause pattern tests at most six. Each gadget therefore uses a product of only constantly many coordinate primes, which is the key to the size bound in § 10. All patterns are tested at the same index $x$; the feasibility argument combines their contributions using the common timing, utilization, and value constraints.

Table 1 collects the notation used throughout the reduction.

Symbol	Meaning
$X, Y$	existential and universal source variables
$\alpha, \beta$	assignments to $X$ and $Y$
$\varphi$	source 3-DNF formula
$F = \neg\varphi= C_1 \land\cdots\land C_m$	counterexample 3-CNF formula
$n, u, m$	numbers of $X$-variables, $Y$-variables, and clauses
$A, V(A), K$	selected task set, its value, and the target
$z, p_z$	CRT coordinate and its assigned prime
$x$	integer demand-window index
$\rho, (a_\rho, b_\rho)$	residue pattern and its compiled congruence
$G(a,b,w)$	full congruence gadget of weight $w$
$H(p,w)$	single-task max-residue selector gadget
$\Lambda, h$	block length and early-window threshold
$t_i, f_i$	true and false CRT coordinates for $x_i$
$\tau_i^t, \tau_i^f$	optional true and false selector tasks
$q, S$	selector weight and local spike budget
$W_0, V_0$	anchor weight and forced-task value

CRT Demand Gadgets

The reduction needs a scheduling object that recognizes a conjunction of modular conditions at one time. A coordinate prime stores one logical digit, a residue pattern combines several digits, and the CRT compiles that pattern into one congruence class. A full gadget $G$ realizes the congruence as exact baseline demand plus a residue-triggered spike. The single-task gadget $H$ provides the corresponding compact interface for an optional selector: when its max residue matches, its spike is exact; when the residue does not match, its demand is bounded above by the baseline term. This section defines those interfaces, explains the fixed earlier-deadline construction, proves their demand behavior, and identifies the only DBF test-length forms needed later.

Notation. A plain $x$ denotes the integer demand-window index, also called a CRT timestamp below. It specifies coordinate residues; the actual interval length is denoted by $\ell$. The symbol $r$ indexes a task position inside a full gadget. Formula variables always carry subscripts, as in $x_i$ and $y_j$.

Prime Coordinates and Residues

This subsection defines the CRT representation used to encode universal assignments and to expose local consistency states. Each logical coordinate $z$ receives a distinct prime $p_z$. The two residues used for Boolean encodings are

An arbitrary timestamp may have another residue; such a timestamp is non-Boolean for that coordinate. Define the total indicator

Therefore $\chi_z(x) = 1$ says exactly that the max residue $p_z - 1$ is present. The value $\chi_z(x) = 0$ does not by itself encode false: the residue may be 0, but it may also be non-Boolean. Exact Boolean encodings will therefore be identified separately.

A finite pattern $\rho$ specifies exact residues for a set of coordinates $Z_\rho$. Let

Because the coordinate primes are pairwise coprime, the CRT gives a unique residue $a_\rho\pmod{b_\rho}$ satisfying all requirements in $\rho$. Define

We say that a timestamp $x$ matches the pattern $\rho$ if it satisfies every residue requirement in $\rho$, equivalently if $\chi_\rho(x) = 1$. Matching the coordinate’s max residue means $x \equiv p_z - 1 \pmod{p_z}$. Failing to match this max residue does not imply that the residue is zero. For later use, define two further total indicators:

Full Gadget

Fix integers $\Lambda$, $h$, $w$ with $2 \le h \le\Lambda$ and $w \ge1$. The concrete values are chosen in § 8. The common timing scale $\Lambda$ divides the test lengths into blocks. For each nonnegative integer index $x$, call $x\Lambda$ the baseline test length and $x\Lambda+ h - 1$ the early test length. Thus $h - 1$ is the offset of the early test after the preceding block boundary. For $0 \le a < b$, the full gadget $G(a,b,w)$ contains one task for each $r \in\{1,\ldots,b\}$, with timing parameters

Task values are assigned in Section 8. The component with $r = a + 1$ is the special task. For comparison, consider a reference specification with the same execution times and periods and deadline $r\Lambda$ for every component. The constructed specification instead gives the special task the fixed relative deadline $a\Lambda+ h - 1$, earlier than its reference deadline $(a + 1)\Lambda$ by

Here $h - 1$ is the offset after the preceding boundary $a\Lambda$, whereas $\delta$ is the difference between the two deadlines. This weighted and rescaled form of the congruence-class construction of Ekberg and Yi [13] produces one extra weight-$w$ contribution at early windows whose index satisfies $x \equiv a \pmod b$. The parameter verification later establishes $C_r \le D_r \le T_r$ for all instantiated tasks.

Max-Residue Gadget

An optional selector must be one task, because the target problem permits selection of individual tasks rather than indivisible groups. For a prime $p$, define the single-task gadget $H(p, w)$ by its timing tuple

Its value is assigned in Section 8. We say that $x$ matches $H(p, w)$ when $x \equiv p - 1 \pmod p$. At that residue its demand at the early window is exactly $wx + w$; otherwise its demand is at most $wx$, as proved below.

Gadget Timeline Intuition

We compare the reference and constructed specifications to explain the extra demand at an early test length. The DBF is evaluated on interval lengths; the timelines below show the synchronous minimum-separation release pattern that realizes each specification’s demand count.

Both specifications have $b$ tasks with execution time $w$ and period $b\Lambda$. The reference deadlines are $\Lambda, 2\Lambda, \ldots, b\Lambda$, so the repeated deadline events contribute one weight-$w$ job at every positive multiple of $\Lambda$. The constructed specification has the same deadlines except that component $a + 1$ has relative deadline $a\Lambda+ h - 1$. Each relative deadline is fixed before execution and applies to every job of its task.

For example, take $b = 5$, $a = 2$, $\Lambda= 10$, $h = 4$, and $w = 1$. The reference deadlines in the first period are $10, 20, 30, 40, 50$; the constructed deadlines are $10, 20, 23, 40, 50$. At length $20$, both specifications demand two units. At length $23$, the reference specification still demands two, but the constructed specification demands three. The early test extends the baseline by $h - 1 = 3$, while the special task’s constructed deadline is earlier than its reference deadline by $\Lambda- h + 1 = 7$.

In general, the special task has a deadline event in $(x\Lambda, x\Lambda+ h - 1]$ exactly when $x \equiv a \pmod b$. No non-special deadline lies in this interval because $0 < h - 1 < \Lambda$. Figure 3 illustrates the resulting extra demand in the matching case. The one-task gadget $H(p, w)$ uses the same timing principle to detect its max residue, but its nonmatching baseline is only an upper bound.

Gadget Demand Behavior

Additionally,

and

The final inequality is an equality whenever $x\equiv p-1$ (mod $p$).

Proof. The full gadget contains $b$ tasks, each with utilization $w/(b\Lambda)$, while the max-residue gadget has utilization $wp/(p\Lambda)$. Therefore each gadget has total utilization $w/\Lambda$.

For $G(a,b,w)$, all $b$ tasks have period $b\Lambda$. The reference specification has deadline $r\Lambda$ for component $r$, while the constructed specification gives the special component $a+1$ the fixed earlier deadline $a\Lambda+h-1$. Because $0<h-1<\Lambda$, a special job is counted at a baseline length $x\Lambda$ under the constructed specification exactly when it is counted there under the reference specification. The other deadlines coincide in the two specifications. The reference specification counts exactly one weight-$w$ job for each integer position $1,\ldots,x$, so $\operatorname{dbf}(G(a,b,w),x\Lambda)=wx$.

Extending the baseline length to $x\Lambda+h-1$ counts no additional job of a non-special task because the extension is shorter than $\Lambda$. The special job with release index $k\ge0$ is counted at the early length exactly when

or equivalently $a+kb\le x$. Compared with the baseline condition $a+1+kb\le x$, the early test therefore counts one additional job exactly when $x\equiv a$ (mod $b$).

For $H(p,w)$, the synchronous minimum-separation release pattern has deadline events $(p-1)\Lambda+h-1+kp\Lambda$ for integers $k\ge0$. At the early window $x\Lambda+h-1$, the job with index $k$ is counted exactly when $p-1+kp\le x$, so the count is $\lfloor(x+1)/p\rfloor$. If $x\equiv p-1$ (mod $p$), then $p$ divides $x+1$ and the demand is

Otherwise, writing $s = x \bmod p < p - 1$, the count is $(x-s)/p$, so the demand is $w(x-s) \le wx$. At the baseline window $x\Lambda$, job $k$ is counted exactly when $p-1+kp \le x-1$, because $0 < h-1 < \Lambda$; the count is therefore $\lfloor x/p \rfloor$, and the demand is $wp\lfloor x/p \rfloor\le wx$.

Spike accounting. A full gadget $G(a,b,w)$ matches $x$ when $\chi_{a,b}(x) = 1$. Its demand beyond its exact baseline $wx$ is $w\chi_{a,b}(x)$. For $H(p,w)$, the quantity $w\chi_p(x)$ is a spike allowance: when $x$ matches its max residue, demand is exactly $wx+w$; otherwise demand may be smaller than $wx$, so zero is an upper bound on the excess rather than an exact contribution.

Upper-bound arguments may sum these allowances. Lower-bound arguments use the CRT to choose a timestamp at which every selected selector matches, making its bound exact. If the selected gadgets have total weight $\Lambda$, then

Only $h-1$ units fit beyond $x\Lambda$. At a timestamp where all required bounds are attained, an aggregate spike of $h$ produces demand $\ell+1$ at $\ell=x\Lambda+h-1$, violating feasibility.

Relevant DBF Test Lengths

Proof. For a full gadget, $D$ is either $r\Lambda$ or $a\Lambda+h-1$, and $T=b\Lambda$. For a max-residue gadget, $D=(p-1)\Lambda+h-1$ and $T=p\Lambda$. Adding $kT$ preserves the claimed form in both cases.

Together with Lemma 1, this proves that the two displayed families of lengths contain every DBF test needed for feasibility.

The gadgets now provide the temporal part of the reduction: a timestamp determines which residue patterns match, and the matching patterns determine the early-window spikes. What the gadgets do not yet guarantee is that a selected set represents one valid existential assignment. The next section provides that local consistency condition.

Local Selector Lock with Polynomial Weights

The construction must force every feasible selection $A$ meeting the value target to choose exactly one truth selector for each existential variable. Recall that meeting the target means $V(A) \ge K$; feasibility is a separate requirement. Value and utilization first force exactly $n$ optional selectors in total, but one variable could still receive both selectors while another receives neither.

The selector lock is local to $x_i$ in the sense of Definition 3: its helpers and selectors test only the two coordinates $t_i,f_i$. At an exact both-match state, a duplicated choice produces excess demand. At an exact neither-match state, the helpers for a missing choice fill its local budget and provide no compensating slack. CRT realizes these per-variable states at one common index. This section proves the per-variable demand inequalities; Lemma 9 combines them after § 8 fixes the global timing and value parameters.

Selection Choices and Timestamp Tests

For each existential variable $x_i$, create two CRT coordinates

with distinct primes $p_{t_i}$ and $p_{f_i}$. These coordinates belong to the timestamp encoding; they are not tasks and are not selection choices.

The selection choices are two optional selector tasks. For a common weight $q$, define

Selecting $\tau_i^t$ encodes $x_i=\mathrm{true}$, while selecting $\tau_i^f$ encodes $x_i=\mathrm{false}$. The symbols $\tau_i^t,\tau_i^f$ denote tasks; $t_i,f_i$ denote the CRT coordinates inspected by those tasks.

The timestamp tests those claims. At an early window indexed by $x$, $\tau_i^t$ has an exact spike of $q$ when $x\equiv p_{t_i}-1\pmod{p_{t_i}}$, and $\tau_i^f$ has an exact spike of $q$ when $x\equiv p_{f_i}-1\pmod{p_{f_i}}$. A selector that is not selected contributes no demand, regardless of the timestamp residue.

Exact Local Timestamp States

Define

The four indicator states are

These are timestamp states, not selection cases. We call $x$ exact for $x_i$ when both residues are Boolean:

At an exact timestamp, $(1,0)$ and $(0,1)$ encode true and false, while $(1,1)$ and $(0,0)$ are the both-match and neither-match test states. These states describe the timestamp and are not four selection choices. In particular, $(0,0)$ is not an optional “choose neither” gadget. The mandatory $(0,0)$-helper introduced below supplies the full local spike budget $S$ at an exact neither-match timestamp. Lemmas 6 and 9 use this contribution to ensure that a variable with no selected selector creates no slack that could offset the excess demand produced by a variable with both selectors. At a non-exact timestamp, an indicator value of zero does not necessarily mean that the residue is zero. This is why the exactness condition is stated separately.

Selector Weight and Local Budget

Recall that $m$ is the number of clauses in $F=C_1\land\cdots\land C_m$. The entire clause layer can change the early-window spike by at most $m$. Set

Therefore one selected selector of weight $q$, together with a unit helper, exactly fills the intended local budget $S$. A duplicate selector creates an excess of $q=m+1$, which cannot be hidden by losing at most $m$ units from the clause layer.

Four Exact-State Helper Gadgets

Let

For $s\in\{10,01,11,00\}$, let $a_i^s\pmod{b_i}$ be the CRT residue that realizes the corresponding exact pair of Boolean residues. Add the four full helper gadgets

Each expression denotes a full gadget and therefore expands into $b_i$ ordinary sporadic tasks. These helper tasks are not optional selectors. § 8 assigns every component task the high value $V_0$, and Lemma 7 proves that every selection meeting the value target must include all four helpers. Therefore “forced helper” describes a property proved later, not an assumption made here.

At an exact timestamp, exactly one of the four helper patterns matches. The matching helper contributes a spike of 1 in states $(1,0)$, $(0,1)$, and $(1,1)$, and a spike of $S$ in state $(0,0)$. At a non-exact timestamp, none of the four exact-state helpers matches.

The intended lock is summarized in Figure 4. A valid one-selector selection stays within the local budget $S$ at every timestamp. If both selectors are selected, the exact state $(1,1)$ activates both selector spikes and produces a local spike of $S+q$, exceeding the budget by $q$. If neither selector is selected, the exact state $(0,0)$ still contributes the full $S$, so the missing variable creates no slack that could absorb the duplicate’s excess. Therefore $(1,0)$, $(0,1)$, $(1,1)$, and $(0,0)$ are timestamp tests for valid, duplicate, and missing selections, and not four selection tests.

Local Spike Allowance and Budget Margin

For a selection $A$ that contains all four exact-state helper gadgets for $x_i$, let $L_i(A)$ denote those helpers together with whichever of $\tau_i^t,\tau_i^f$ are selected. Define

The local early-window spike allowance is

The four helpers have total baseline weight $S+3$, and the selected selectors have total baseline weight $q s_i(A)$. Additivity of demand and Lemma 2 therefore give

Every helper term in $L_i(A,x)$ is an exact spike contribution. A selector term is an upper allowance in general and is exact when that selected selector matches its max residue. Therefore the inequality is an equality at each timestamp used below to establish a lower bound.

Define the signed local budget margin

A positive value is unused spike allowance, zero means that the allowance exactly fills the local budget, and a negative value is an overage. The next three lemmas bound this margin for valid selections at every timestamp and compute it at the exact states used to expose duplicate and missing selections.

Valid-Selection Lemma

Proof. Assume first that only $\tau_i^t$ is selected. If $x$ is exact for $x_i$, exactly one helper pattern matches, and Table 2 lists all possibilities. Therefore $L_i(A,x)\le S$ and $\mu_i(A,x)\ge0$ in every exact state.

Table 2: Local spike allowances when only $\tau_i^t$ is selected. The selector column is an upper allowance; it is an exact excess when that selector matches.

State $\sigma_i(x)$	Helper	$\tau_i^t$	$L_i(A,x)$	$\mu_i(A,x)$
(1, 0)	1	$q$	$S$	0
(0, 1)	1	0	1	$q$
(1, 1)	1	$q$	$S$	0
(0, 0)	$S$	0	$S$	0

If $x$ is not exact for $x_i$, none of the four helper patterns matches. Therefore

so $L_i(A,x)\le q<S$ and $\mu_i(A,x)\ge S-q=1$.

If only $\tau_i^f$ is selected, interchange the $t_i$- and $f_i$-coordinates. At exact timestamps its selector allowance is $q$ in states $(0,1)$ and $(1,1)$, and zero in states $(1,0)$ and $(0,0)$; at non-exact timestamps, $L_i(A,x)=q\chi_{f_i}(x)\le q<S$. Therefore the same two inequalities hold for every $x$. The displayed DBF bound now follows from $s_i(A)=1$ and the local-demand inequality above. $\square$

Equality cases used later. If only $\tau_i^t$ is selected, exact states $(1,0)$, $(1,1)$, and $(0,0)$ have $L_i(A,x)=S$. If only $\tau_i^f$ is selected, exact states $(0,1)$, $(1,1)$, and $(0,0)$ have $L_i(A,x)=S$. At the matching states $(1,0)$ and $(0,1)$, respectively, the selected selector is active, so the local DBF upper bound is attained.

Duplicate-Selection Lemma

Proof. At exact state $(1,1)$, the unique matching helper contributes $1$, and both selected selectors match their max residues. Thus $L_i(A,x) = 1 + 2q = S + q$ and $\mu_i(A,x) = -q$. By Lemma 2, the helper demand is exactly $x(S + 3) + 1$, and each selector contributes $qx + q$. Summing gives the claimed DBF identity.

Missing-Selection Lemma

Proof. At exact state $(0,0)$, only the weight-$S$ helper matches. Since no selector is selected, $L_i(A,x) = S$ and $\mu_i(A,x) = 0$. Lemma 2 gives the exact helper demand $x(S + 3) + S$, proving the claimed DBF identity.

Two-Variable Selector Example

Let $n = 2$ and $m = 2$, so $q = 3$ and $S = 4$. Consider first the well-formed selection

At an exact timestamp placing $x_1$ in state $(1,0)$ and $x_2$ in state $(0,1)$, each variable contributes its full local budget $S$. The $X$-layer spike is therefore

Now consider the malformed selection

which selects both selectors for $x_1$ and none for $x_2$. It still contains exactly $n = 2$ selectors, so the global selector count alone does not reject it. By the CRT, choose one timestamp placing $x_1$ in exact state $(1,1)$ and $x_2$ in exact state $(0,0)$. The local spikes are

Therefore the $X$-layer spike is

which exceeds its intended budget $2S = 8$ by $q = 3$.

This local calculation becomes a DBF violation after the global parameters are fixed. § 8 sets

In the proof of Lemma 9, the CRT timestamp is also chosen so that the anchor contributes $W_0$, the $Y$-validity layer contributes $u$, and every selected selector needed by the malformed selection matches. Even if the clause layer contributes nothing, the total spike is at least

At the early window $\ell= x\Lambda+ h - 1$, Lemma 2 therefore gives

which is a deadline miss. This is the precise connection between the local selector calculation, the generated tasks, and the global DBF inequality.

With the temporal gadgets and local selector lock in place, the reduction can now be assembled layer by layer. The construction below chooses the global weights so that the local budget $S$, the logical clause contribution, and the one-unit feasibility gap share one common early-window threshold.

Reduction Construction

We now specify the residue patterns and assemble the task inventory summarized in § 5.2.

Residue Patterns

Assign the first $2n+u$ primes to the coordinates $t_i$, $f_i$, $y_j$. For each pattern, compute its canonical CRT residue $0 \le a_\rho< b_\rho$, where $b_\rho$ is the product of its coordinate primes. These computations take polynomial time; § 10 bounds the primes, moduli, and explicit output size.

The anchor $G(0,1,W_0)$ matches every timestamp. Let $\mathcal{P}$ contain the four weighted $X$-helper patterns per variable from § 7, the $Y$-validity patterns, and the clause patterns defined below. Patterns form an indexed multiset, so repeated congruences retain their separate demand contributions.

For each $y_j$, include two unit-weight validity patterns, with residues $0$ and $p_{y_j} - 1$, encoding false and true. At most one matches at any timestamp, and neither matches a non-Boolean residue.

For each clause $C_k$, let $Z_k$ contain one coordinate $y_j$ for each universal variable occurring in that clause and both $t_i$, $f_i$ for each existential variable occurring in it. Set $b_k = \prod_{z \in Z_k} p_z$. For each of the clause’s seven satisfying assignments $\gamma$, include the unit-weight pattern $a_{k,\gamma}$ (mod $b_k$) encoding $\gamma$. Existential true and false require the exact states $(1,0)$ and $(0,1)$, respectively; universal true and false require residues $p_{y_j} - 1$ and $0$. The seven patterns are pairwise disjoint. At a valid Boolean encoding, exactly one matches if the clause is satisfied, and none otherwise. Reading both existential coordinates prevents states $(1,1)$ and $(0,0)$ from matching a clause pattern that mentions that variable.

Assembly

Instantiate each $\rho\in\mathcal{P}$ as $G(a_\rho,b_\rho,w_\rho)$, include the anchor and optional selectors, and use the timing constants, task multisets, and value assignment defined in § 5.2. The mandatory pattern weights sum to $B_{\mathrm{mand}} = \sum_{\rho\in\mathcal{P}} w_\rho= n(S + 3) + 2u + 7m$, excluding the anchor. The individual task counts are $M = 1 + \sum_{\rho\in\mathcal{P}} b_\rho$, $|\Gamma_{\mathrm{opt}}| = 2n$, and $|\Gamma| = M + 2n$; $m$ counts clauses. These patterns therefore complete the instance $(\Gamma, K)$ specified in the overview. Figure 5 summarizes the early-window gap used in the correctness proof.

Correctness Proof

The proof has two phases:

1. The structural phase identifies the only possible shape of a feasible selection meeting the value target. Value forces every mandatory task (Lemma 7), value and utilization together force exactly $n$ selectors in total (Lemma 8), and the local lock distributes them

one per existential variable (Lemma 9). The selection therefore defines one assignment $\alpha$ (Lemma 10).

2. The logical phase relates that assignment to the source formula. The forward direction proves that a winning $\alpha$ gives a feasible selection. The reverse direction turns any losing response $\beta$ into a violating early window (Lemmas 11 and 12).

As everywhere in the paper, $A$ denotes a selected task set, while $S$ is the local budget constant of Section 7.

Mandatory Selection Lemma

Proof. There are $M$ mandatory tasks, each with value $V_0$, and $2n$ optional selector tasks, each with value 1. If a selection excludes even one mandatory task, its value is at most

Since $V_0 > 2n$, this is strictly less than

Therefore every selection meeting the value target includes all mandatory tasks.

Utilization Squeeze Lemma

Proof. By Lemma 7, every selection meeting the value target contains all mandatory tasks. Since the mandatory tasks contribute exactly $MV_0$ value, the target

forces the selection to contain at least $n$ optional selectors.

Let $s$ be the number of selected optional selectors. The mandatory gadgets contribute utilization

and each selected optional selector contributes $q/\Lambda$. Therefore

Since

feasibility implies $U \le1$ and hence $s \le n$. Combining the value requirement $s \ge n$ with the utilization requirement $s \le n$ gives $s = n$. Therefore every feasible selection meeting the value target contains exactly $n$ selected optional selectors.

Local Selector-Lock Lemma

With the timing constants in place, the local lemmas of § 7 combine into the global selector lock.

Proof. Consider a feasible selection A meeting the value target. By Lemma 8, A contains exactly $n$ selected optional selectors. Suppose for contradiction that both selectors are selected for some variable, and let $d \ge1$ be the number of variables with both selectors selected. The number of variables with neither selector selected is also $d$. Relative to the intended one selector per variable, each duplicate contributes one excess selector and each missing variable contributes one deficit. Use the CRT to choose a timestamp $x$ satisfying the following exact residue requirements:

• every variable with both selectors selected is placed in state $(1,1)$;

• every variable with neither selector selected is placed in state $(0,0)$;

• every variable with exactly one selected selector is placed in a budget-reaching valid state: $(1,0)$ if $\tau_i^t$ is selected and $(0,1)$ if $\tau_i^f$ is selected; and

• every universal coordinate $y_j$ is placed at the residue $0$ (mod $p_{y_j}$), which is one of its Boolean residues.

Each requirement fixes one residue modulo its coordinate prime, and no coordinate receives two different requirements. Because all coordinate moduli are distinct primes, they are pairwise coprime. The Chinese Remainder Theorem therefore gives a simultaneous solution that is unique modulo the product of the coordinate primes. Choose the least nonnegative representative as $x$. As noted in § 8, this representative is computable in polynomial time by the constructive CRT algorithm.

At the chosen timestamp, every variable with exactly one selected selector is in the matching valid state for that selector. The equality cases following Lemma 4 therefore give $L_i(A,x)=S$ for each such variable. Lemma 6 gives $L_i(A,x)=S$ for each missing variable, and Lemma 5 gives $L_i(A,x)=S+q$ for each duplicated variable. Because there are $d$ duplicated variables, $d$ missing variables, and $n-2d$ one-selector variables,

These are actual spike contributions, not just upper allowances: every selected selector matches its max residue at the chosen timestamp, and every selected helper state is exact.

The $Y$-validity layer contributes its exact spike $u$, because every universal coordinate is at a Boolean residue. The dummy anchor contributes its exact spike $W_0$, and the clause-layer spike is nonnegative. Moreover, every mandatory full gadget contributes its exact baseline demand and the $n$ selected selectors contribute total baseline demand $xnq$. Therefore Lemma 2 gives

where the equality uses $q=m+1$ and $h=W_0+nS+u+m$. This contradicts feasibility, so no variable has both selectors selected. Finally, $A$ contains exactly $n$ selectors by Lemma 8; because there are $n$ variables and each has at most one selector, every variable has exactly one selector.

Assignment Extraction Lemma

The structural phase is now complete: a feasible selection meeting the value target is not just a set of the right cardinality, but a unique assignment $\alpha$. The remaining question is logical. The forward direction shows that a winning $\alpha$ survives every early-window test. The reverse direction converts any losing response $\beta$ into one explicit violating window.

Forward Direction

Figure 5. The dummy anchor contributes $W_0$. By Lemma 4, the total $X$-layer spike allowance is at most $nS$. The $Y$-validity layer contributes at most $u$, since at most one of the two validity patterns for each $y_j$ can match. The clause layer contributes at most $m$, since at most one satisfying pattern for each clause can match. Therefore

Both $\operatorname{dbf}(A_\alpha, x\Lambda+ h - 1)$ and $x\Lambda$ are integers, so $\Delta_\alpha(x)$ is an integer. As a result, this bound leaves only the safe case $\Delta_\alpha(x) \le h - 1$ and the equality case $\Delta_\alpha(x) = h$. If $\Delta_\alpha(x) \le h - 1$, then

as required.

Ruling out $\Delta_\alpha(x) = h$. Suppose that $\Delta_\alpha(x) = h$. The preceding upper bound was obtained by adding the anchor contribution $W_0$, the $X$-layer bound $nS$ from Lemma 4, the $Y$-validity bound $u$, and the clause-layer bound $m$ from Section 8. Because these four bounds sum to $h$, equality can hold only if every individual layer bound is tight. As a result:

• every $y_j$ is at a Boolean residue, defining an assignment $\beta$;

• every clause of $F$ has one matched satisfying pattern; and

• every $x_i$ attains its full local spike allowance $S$.

Consider any matched clause pattern that mentions $x_i$. It fixes the exact pair $\sigma_i(x) = (1,0)$ or $(0,1)$. If the fixed pair disagreed with the selected selector, say the pattern fixes $(0,1)$ while $\tau_i^t$ is selected, then at this timestamp the helper contributes 1 and the selector does not spike, so $x_i$ contributes $1 < S$, contradicting tightness of the $X$-layer. Therefore every matched clause pattern agrees with $\alpha$ on the existential variables it mentions and with $\beta$ on the universal variables it mentions, and the matched patterns certify that

This contradicts the assumption that $\alpha$ is winning. Therefore $\Delta_\alpha(x) \ne h$. Since $\Delta_\alpha(x)$ is an integer and the preceding bound gives $\Delta_\alpha(x) \le h$, it follows that $\Delta_\alpha(x) \le h - 1$. Therefore

at every early window.

Reverse Direction

Proof. Suppose a feasible selected subset $A$ meets the value target $K$. By Lemmas 7, 8, and 10, $A$ selects all mandatory tasks and exactly one selector for every existential variable. Let $\alpha$ be the extracted assignment to $X$.

From a losing existential assignment to a DBF violation. Assume for contradiction that $\alpha$ is not winning. Then some assignment $\beta$ to $Y$ satisfies

For each $x_i$, require both coordinate residues to be Boolean and impose $\sigma_i(x) = (1,0)$ when $\alpha(x_i) = \text{true}$ and $\sigma_i(x) = (0,1)$ otherwise. For each $y_j$, impose the Boolean residue encoding $\beta(y_j)$. These conditions fix one residue modulo each distinct coordinate prime, so the CRT gives a timestamp $x$ satisfying all of them simultaneously.

Consider the early window

The dummy anchor contributes its exact spike $W_0$. Every selected optional selector matches its max residue. By the equality cases following Lemma 4, each existential variable’s matching helper and selected selector attain an actual local spike of $S$. The $X$-layer spike is therefore exactly $nS$.

By the $Y$-validity construction in § 8, exactly one validity gadget matches for each encoded $y_j$, giving a total spike of $u$. Because $(\alpha,\beta)$ satisfies every clause of $F$, the clause construction in § 8 makes exactly one satisfying pattern match for each clause, giving a total clause spike of $m$. Therefore the actual spike beyond the baseline $x\Lambda$ is

All selected selectors match at this timestamp, so the selector bounds in Lemma 2 are equalities. That lemma therefore gives

This is a DBF violation and contradicts feasibility. Hence no losing response $\beta$ exists, and $\alpha$ is winning.

This completes the logical part of the reduction. The remaining task is to verify that the CRT construction does not cause an exponential increase in the numerical parameters or number of tasks.

Polynomial Boundedness and Unary Encoding

Global CRT timestamps may have exponentially large magnitude, but they are not task parameters. The following lemma bounds the explicit task expansion and all generated integers.

Proof. Put $k = 2n + u$. The first $k$ primes can be enumerated in polynomial time and satisfy $p_{\max} = O(k \log k)$ [23]. An $X$-helper reads two coordinates, a $Y$-validity pattern one, and a clause pattern at most six. Their moduli are therefore bounded by $p_{\max}^{2}$, $p_{\max}$, $p_{\max}^{6}$, respectively. Since a full gadget contains one task per modulus position, the total task count is at most

which is polynomial in the source encoding length.

The definitions make $q$, $S$, $W_0$, $B_{\mathrm{mand}}$, $\Lambda$, $h$ polynomially bounded. Full-gadget parameters are $C = w$, $T = b\Lambda$, and either $D = r\Lambda$ or $D = a\Lambda+ h - 1$, where $a < b$, $1 \le r \le b \le p_{\max}^{6}$, and $w \le\max\{W_0,S\}$. Selector parameters are $(qp, (p-1)\Lambda+ h - 1, p\Lambda)$, with $p \le p_{\max}$. Therefore all timing parameters have polynomial magnitude. Values are $V_0 = 2n + 1$ or $1$, and $K = MV_0 + n$ is polynomially bounded by the task-count bound.

The identity $\Lambda- h = 3n + u + 6m + nq \ge0$ gives $h \le\Lambda$. Since $n \ge1$, $S \ge2$, and $W_0 \ge1$, also $h \ge2$ and $h - 1 \ge\max\{W_0,S\}$. Every full-gadget deadline is at least $h - 1$, so $C \le D$. Non-special deadlines satisfy $D = r\Lambda\le b\Lambda= T$; special deadlines satisfy $D = a\Lambda+ h - 1 < (a+1)\Lambda\le b\Lambda= T$. For a selector, $p \ge2$ gives

Therefore every generated task satisfies $C \le D \le T$. Computing the local CRT residues and expanding these polynomially bounded gadgets takes polynomial time. Since every output integer has polynomial magnitude, the same holds for unary output.

The bound can still be large, though: the clause layer contains at most $7mp_{\max}^{6} = O(m[(2n+u)\log(2n+u)]^{6})$ tasks. The construction is only for the complexity proof and is not intended as a practical instance generator.

Main Result

Discussion

Unless the polynomial hierarchy collapses, $\mathrm{VTS}$ belongs to neither NP nor coNP. Hardness persists with polynomially bounded numerical parameters, so an exact algorithm polynomial in task count and parameter magnitudes would imply $P = \Sigma^{P}_{2}$ and collapse the hierarchy to P. The disabled-option MIS model of § 2 is likewise $\Sigma^{P}_{2}$-complete. Approximation, online selection, multiprocessor platforms, and tractable restricted families remain separate questions.

Conclusion

We proved that $\mathrm{VTS}$ for sporadic tasks on one preemptive processor is $\Sigma^{P}_{2}$-complete for both constrained and arbitrary deadlines, including unary encoding. CRT demand gadgets represent universal responses, while local selector locks enforce one existential truth choice per variable. The construction uses constrained deadlines and has polynomial task count and numerical parameters.

For comparison, the analogous selection problem under a supplied fixed task-priority order is NP-complete for implicit or constrained deadlines. Membership follows by guessing the selected set and response-time fixed points no larger than the corresponding deadlines; these certificates can be checked in polynomial time. For hardness, assign every task value 1 and set $K = |\Gamma|$, forcing all tasks to be selected. NP-hardness then follows from fixed-priority schedulability [14].

Funding

This work was supported in part by the U.S. National Science Foundation under Grants 2211641, 2246672, 2442078, and 2502855, and by the Swedish Research Council under Grant 2023-04586.

Author contributions

The original research problem was conceived and formulated by K.Y. and Z.G. C.H. identified the relevant complexity class, developed the $\Sigma_{2}^{P}$-completeness proof, and prepared the manuscript. All authors contributed to refining the proof strategy, strengthening the motivation and presentation of the technical results, and clarifying the scope of the mathematical claims. All authors critically reviewed the manuscript and its mathematical arguments, approved the final version, and agreed to be accountable for the integrity of the work.

Use of generative AI

OpenAI Codex was used to assist with manuscript proofreading, LaTeX formatting tweaks, and debugging of text-based explanatory diagrams in TikZ. The authors reviewed all outputs and take responsibility for the accuracy of all output. No generative image model was used. All figures are original diagrams compiled from LaTeX/TikZ source. No LLM was used in the generation of the content of the paper itself in any sort of generative context, only proofreading and LaTeX/TikZ debugging.

Source Normal Form

The reduction assumes a source instance of the form

where $\varphi$ is a 3-DNF formula whose terms have exactly three literals over distinct variables. This is a standard $\Sigma_{2}^{P}$-complete normal form ([27, 28, 24]). One route is to start from the complement of the usual $\forall\exists$-3CNF problem. Negating the inner CNF produces a DNF, and the leading quantifiers swap to the required $\exists\forall$ form.

Terms with fewer than three literals can be padded using fresh universally quantified variables. If a term $\theta$ has $r < 3$ literals, introduce $3-r$ fresh variables $z_{1},\ldots,z_{3-r}$ and replace $\theta$ by the disjunction over all assignments to those variables:

where $z_{j}^{1}=z_{j}$ and $z_{j}^{0}=\neg z_{j}$. For any assignment to the fresh variables, exactly one pattern $\bigwedge_{j}z_{j}^{\pi_{j}}$ is true, so the padded disjunction is true exactly when $\theta$ is true, and the formula is preserved. Contradictory terms are deleted, and duplicate literals inside a term are removed before padding. Degenerate always-true or always-false cases can be mapped explicitly to fixed instances: the one-task system $\Gamma=\{(1,1,1,1)\}$ with $K=1$ is a yes-instance, while the same system with $K=2$ is a no-instance.