<p>A <a href="http://eccc.hpi-web.de/report/2015/148/">new preprint</a> by Carmosino et al. introduces the Nondeterministic Strong Exponential Time Hypothesis (NSETH) which makes the conjecture that there are no $\text{NTIME}[2^{(1-\varepsilon) n}]$ algorithms for DNF-TAUT. NSETH is of course an even stronger assumption than "NETH" which you ask about, and still appears to be consistent with everything we know so far. The authors use this conjecture to show that a number of other fine-grained complexity assumptions are unlikely to be reducible to each other.</p>

CC BY-SA 3.0
2015-09-12T21:37:37.877Z
2015-09-12T21:37:37.877Z
Huck Bennett
<p>It is possible ;-)</p>

<p>It would give new circuit lower bounds.  Since you are making a pretty strong assumption this could follow from the <a href="http://www.cs.sfu.ca/~kabanets/Research/ikw.html">seminal work by Impagliazzo, Kabanets, and Wigderson</a>, I haven't checked.</p>

<p>If you use <a href="http://www.stanford.edu/~rrwill/improved-algs-lbs2.pdf">Williams' approach</a>, tightened <a href="http://www.ccs.neu.edu/home/viola/papers/explicit.pdf">here</a>, you get a lower bound of $n^{1+\Omega(1)}$ for a function on $n$ bits in the class E$^{NP}$.  (For this approach, a fast co-nondeterministic algorithm for satisfibility is sufficient, as you are postulating.)  Specifically, the <a href="http://www.ccs.neu.edu/home/viola/papers/explicit.pdf">latter paper</a> shows that a lower bound for size $s$ follows from a satisfiability algorithm for circuits of size $O(s)$, which we can translate to a 3SAT instance with $O(s)$ variables by Cook-Levin.</p>

<p>It would not directly contradict ETH because that's for deterministic algorithms.</p>

CC BY-SA 3.0
2014-04-09T15:18:08.573Z
2014-04-09T15:18:08.573Z
Manu
<p>Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ?
Are there interesting consequences of such containment?
Would it contradict the Exponential Time Hypothesis?</p>

<sat><exp-time-algorithms><nexp>
$\overline{SAT} \in NTIME(subexp)$?
Igor Shinkar
# $\overline{SAT} \in NTIME(subexp)$?

(Asked by: username_0 on 2014-04-09)

Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ?
Are there interesting consequences of such containment?
Would it contradict the Exponential Time Hypothesis?

**Tags:** sat, exp-time-algorithms, nexp


---

## 2 answers

### Answer by username_2 on 2014-04-09. Score: 17 | Accepted answer

It is possible ;-)

It would give new circuit lower bounds. Since you are making a pretty strong assumption this could follow from the [seminal work by Impagliazzo, Kabanets, and Wigderson](http://www.cs.sfu.ca/~kabanets/Research/ikw.html), I haven't checked.

If you use [Williams' approach](http://www.stanford.edu/~rrwill/improved-algs-lbs2.pdf), tightened [here](http://www.ccs.neu.edu/home/viola/papers/explicit.pdf), you get a lower bound of $n^{1+\Omega(1)}$ for a function on $n$ bits in the class E$^{NP}$. (For this approach, a fast co-nondeterministic algorithm for satisfibility is sufficient, as you are postulating.) Specifically, the [latter paper](http://www.ccs.neu.edu/home/viola/papers/explicit.pdf) shows that a lower bound for size $s$ follows from a satisfiability algorithm for circuits of size $O(s)$, which we can translate to a 3SAT instance with $O(s)$ variables by Cook-Levin.

It would not directly contradict ETH because that's for deterministic algorithms.


---

### Answer by username_1 on 2015-09-12. Score: 10

A [new preprint](http://eccc.hpi-web.de/report/2015/148/) by Carmosino et al. introduces the Nondeterministic Strong Exponential Time Hypothesis (NSETH) which makes the conjecture that there are no $\text{NTIME}[2^{(1-\varepsilon) n}]$ algorithms for DNF-TAUT. NSETH is of course an even stronger assumption than "NETH" which you ask about, and still appears to be consistent with everything we know so far. The authors use this conjecture to show that a number of other fine-grained complexity assumptions are unlikely to be reducible to each other.


---

