Position: Temporal Measurement Interval Determines Computational and Model Complexity in Single-Cell Perturbation Analysis

Single-cell perturbation analysis aims to predict how cellular states change after interventions such as drug treatments or genetic edits. A central difficulty is that pre- and post-perturbation measurements are typically observed as *unpaired* populations, so accurate prediction requires inferring a latent coupling and learning a transition map. In this position paper, we argue that the *measurement time gap* is the key experimental knob controlling both the computational tractability of coupling and the effective model complexity. We identify a critical time gap $\Delta$ that induces a phase transition, under biologically inspired conditions; for "measurement-time $< \Delta$", matching is polynomial-time tractable and the task reduces to supervised learning, whereas for "measurement-time $>\Delta$", recovering the matching is NP-hard in the worst case. The required conditions are restricted isometry of the initial states and temporal smoothness of the transition dynamics. We complement the theory with empirical evidence on synthetic and biological datasets showing a sharp regime change as the time gap increases. Furthermore, we demonstrate that a linear model can match or exceed the performance of higher-capacity neural approaches when our conditions hold.