Visible to the public Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

TitleNondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
Publication TypeConference Paper
Year of Publication2016
AuthorsCarmosino, Marco L., Gao, Jiawei, Impagliazzo, Russell, Mihajlin, Ivan, Paturi, Ramamohan, Schneider, Stefan
Conference NameProceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
PublisherACM
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4057-1
Keywords3-sum, all-pairs shortest path, computational complexity, conditional lower bounds, exponentiation, fine-grained complexity, nondeterminism, pubcrawl, Resiliency, seth, theoretical cryptography
Abstract

We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both refuting and proving NSETH would have interesting consequences. In particular we show that disproving NSETH would give new nontrivial circuit lower bounds. On the other hand, NSETH implies non-reducibility results, i.e. the absence of (deterministic) fine-grained reductions from SAT to a number of problems. As a consequence we conclude that unless this hypothesis fails, problems such as 3-SUM, APSP and model checking of a large class of first-order graph properties cannot be shown to be SETH-hard using deterministic or zero-error probabilistic reductions.

URLhttp://doi.acm.org/10.1145/2840728.2840746
DOI10.1145/2840728.2840746
Citation Keycarmosino_nondeterministic_2016