2-Visits scheduling → 3-Visits scheduling Complexity open

Unsolved

Clone https://github.com/reduction-zoo/three-visits-scheduling to investigate 2-Visits scheduling → 3-Visits scheduling. Read the fixed question and state. Use preparation notes, the test corpus, and verifier if present; otherwise complete Prepare before a reduction attempt. Follow the repository instructions and your AutoResearch pipeline.

Submit a solution

Why this question matters

The question isolates the effect of adding one required visit in a recurring scheduling model.

The finite-visit model constrains first visits and internal gaps without a final-tail condition. Periodic scheduling results therefore do not automatically apply.

The reduction to construct

The source gives task deadlines. Its outputs are finite schedules visiting each task exactly twice, meeting first-visit and successive-gap deadlines with no final-tail condition, or NO-SOLUTION.

A k-Visits solution is a finite word containing each task exactly k times, with its first visit and every successive same-task gap bounded by the task deadline. There is no final-tail constraint. The source has k=2 and the target k=3.

Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.

An extra visit must be forced into a recoverable role; arbitrary placement can invalidate decoding to two visits.

What a complete answer must include

Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.

References

Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.