一句话：系统刻画动态数据竞争预测问题的计算复杂度，识别难解性来源与可高效求解条件。
并发程序因调度非确定性而难以编写，数据竞争是最常见的并发缺陷之一。动态数据竞争预测是检测数据竞争的常用技术：给定一条观测到的无数据竞争 trace t，判断能否将其重排为暴露数据竞争的 trace t*。该问题虽已有三十余年大量实践研究，其复杂度仍不清楚。本文填补这一空白，识别导致难解性的来源，以及问题可高效求解的条件。对于规模为 n、包含 k 个线程的 trace，作者报告了主要结果（摘要未展开具体复杂度界）。
Writing concurrent programs is notoriously hard due to scheduling non-determinism. The most common concurrency bugs are data races, which are accesses to a shared resource that can be executed concurrently. Dynamic data-race prediction is the most standard technique for detecting data races: given an observed, data-race-free trace t, the task is to determine whether t can be reordered to a trace t* that exposes a data-race. Although the problem has received significant practical attention for over three decades, its complexity has remained elusive. In this work, we address this lacuna, identifying sources of intractability and conditions under which the problem is efficiently solvable. Given a trace t of size n over k threads, our main results are as follows.