论文标题
APSP，三角检测和3sum硬度的后果，以确定性和非确定性之间的分离
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
论文作者
论文摘要
我们以否定的线性限制的形式从已知的猜想，3sum和ETH等已知猜想中介绍了含义，其在各自的确定性界限类别中具有非确定性对数甲骨文的线性限制，它们在不同的界定类别中与不同的构构不同，并且它们在输入范围参数中特别表现出对输入范围的依赖性。
We present implications from the known conjectures like APSP, 3SUM and ETH in a form of a negated containment of a linear-time with a non-deterministic logarithmic-bit oracle in a respective deterministic bounded-time class They are different for different conjectures and they exhibit in particular the dependency on the input range parameters.
