Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
DOI10.1145/2840728.2840746zbMath1334.68079MaRDI QIDQ2800573
Ramamohan Paturi, Russell Impagliazzo, Stefan Schneider, Jiawei Gao, Ivan Mihajlin, Marco L. Carmosino
Publication date: 15 April 2016
Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2840728.2840746
computational complexity; nondeterminism; all-pairs shortest path; SETH; 3-sum; conditional lower bounds; fine-grained complexity
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
