Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
arXiv:2011.02428
Abstract
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.
The section on range reduction in a previous version contained a flaw in a proof and therefore it has been removed