ECCC-Report TR15-148https://eccc.weizmann.ac.il/report/2015/148Comments and Revisions published for TR15-148en-usWed, 09 Sep 2015 22:52:08 +0300
Revision 1
| Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility |
Marco L. Carmosino,
Jiawei Gao,
Russell Impagliazzo,
Ivan Mikhailin,
Ramamohan Paturi,
Stefan Schneider
https://eccc.weizmann.ac.il/report/2015/148#revision1We 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.
Wed, 09 Sep 2015 22:52:08 +0300https://eccc.weizmann.ac.il/report/2015/148#revision1
Paper TR15-148
| Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility |
Marco Carmosino,
Jiawei Gao,
Russell Impagliazzo,
Ivan Mikhailin,
Ramamohan Paturi,
Stefan Schneider
https://eccc.weizmann.ac.il/report/2015/148We 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.
Wed, 09 Sep 2015 01:23:24 +0300https://eccc.weizmann.ac.il/report/2015/148