Revision #1 Authors: Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

Accepted on: 9th September 2015 22:52

Downloads: 901

Keywords:

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.

TR15-148 Authors: Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

Publication: 9th September 2015 01:23

Downloads: 1299

Keywords:

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.