Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism

2020/11/04 by Andrzej Lingas, Lingas, Andrzej
Computer Science · #Computational Complexity (cs.CC) #Cryptographic Implementations and Security #Cryptography and Data Security #F.2.2 #FOS: Computer and information sciences #Physical Unclonable Functions (PUFs) and Hardware Security

paper · pdf · doi:10.48550/arxiv.2011.02428

openalex publication_date 2020/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• An Oracle Strongly Separating Deterministic Time from Nondeterministic Time, via Kolmogorov Complexity
• Deterministic 3SUM-Hardness
• Hardness for Triangle Problems under Even More Believable Hypotheses:\n Reductions from Real APSP, Real 3SUM, and OV
• On the Consistency of Circuit Lower Bounds for Non-Deterministic Time
• Higher Lower Bounds from the 3SUM Conjecture