Unary Bin Packing → Two-Slot-Flexible Unit-Job Energy Autarky Complexity open
Unsolved
Why this question matters
Moderate: this would settle the strong-hardness side of the weak-versus-strong boundary posed by the energy-autarky paper for its most restricted flexible jobs, informing when pseudo-polynomial scheduling is possible.
Bredereck et al. (ESA 2026 preprint, Theorems 7–10 and Conclusion) prove weak hardness for flexibility two and strong hardness with larger flexibility. Their flexibility-two plus distinct-release-date plus unit-length case is polynomial, so this card keeps arbitrary overlapping windows. The exact strong status of this slice is an inferred specialization of their explicit boundary question.
The reduction to construct
Input is a unary-encoded multiset of positive item sizes, unary bin capacity B, and a binary or unary bin count m. Output YES exactly if all items fit in at most m bins of capacity B; otherwise NO. Use the standard strong-hardness family with total instance size polynomial in the unary quantities.
Input is a finite horizon, unary-encoded nonnegative energy forecast F(t), and unit-length jobs with unary energy demand e_j and release/deadline windows permitting at most two consecutive start times. No battery and no external energy are allowed. Output YES if each job can be assigned a legal slot and total demand in each slot does not exceed F(t); otherwise NO. The horizon is explicitly represented.
Give a polynomial-size F from unary Bin Packing and truth-preserving G to prove strong NP-hardness of this fixed flexibility-two, no-battery, unit-job target.
High: a bin-packing item may choose among many bins, but each target job has at most two adjacent choices. A polynomial selector must carry one item consistently across a chain without permitting fractional or duplicated placement.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
Literature checked 2026-09-26. Web search 2026-09-26: "flexibility two strongly NP-hard autarky", "Scheduling Tasks towards Energy Autarky weak strong", and board aliases. Read arXiv:2607.03260v1 Sections 3, 5, 6 and 9. No later exact classification found in indexed results. Gate 5 route: use unary-length temporal corridors whose local binary choices encode bin assignment; prove a conservation invariant for every feasible schedule. This mechanism is untested; Gate 6 not assessed.