<p>It is well known that general satisfiability (of polynomially many clauses) is NP-hard, and in fact, it is conjectured that an algorithm deciding instances of SAT takes time nearly $2^n$ on $n$ variables.</p>

<p>I was wondering what, if anything, is known about the hardness of promise variants of the problem, GAP-SAT. Here the promise is that each such Boolean formula $\phi$ is guaranteed to lie in the union of</p>

<p>$$\Pi_{no} = \{\phi: |\{x:\phi(x) = 1 \}| \leq a\} $$ 
and
$$ \Pi_{yes} = \{\phi: |\{x:\phi(x) = 1 \}| \geq b\}$$</p>

<p>for different $0 \leq a = f(n) &lt; b = g(n) \leq 2^n$ fixed functions of $n$. Any references would be appreciated, thanks!</p>

CC BY-SA 3.0
2018-03-23T20:26:09.110Z
Cross-posted from https://mathoverflow.net/q/295997
Emil Jeřábek
CC BY-SA 4.0
2018-07-20T20:18:18.570Z
There is Gap Exponential Time Hypothesis which implies that there is no $2^{o(n)}$ algorithm for this problem for some $\varepsilon, \delta>0$ and $a=\varepsilon |\phi|, b=\delta |\phi|$. See https://eccc.weizmann.ac.il/report/2016/128/ and https://arxiv.org/abs/1607.02986 .
Alex Golovnev
<cc.complexity-theory><sat><promise-problems>
How hard is gapped satisfiability?
shumbo
# How hard is gapped satisfiability?

(Asked by: username_0 on 2018-03-23)

It is well known that general satisfiability (of polynomially many clauses) is NP-hard, and in fact, it is conjectured that an algorithm deciding instances of SAT takes time nearly $2^n$ on $n$ variables.

I was wondering what, if anything, is known about the hardness of promise variants of the problem, GAP-SAT. Here the promise is that each such Boolean formula $\phi$ is guaranteed to lie in the union of

$$\Pi\_{no} = \{\phi: |\{x:\phi(x) = 1 \}| \leq a\} $$
and
$$ \Pi\_{yes} = \{\phi: |\{x:\phi(x) = 1 \}| \geq b\}$$

for different $0 \leq a = f(n) < b = g(n) \leq 2^n$ fixed functions of $n$. Any references would be appreciated, thanks!

**Tags:** cc.complexity-theory, sat, promise-problems

> **Comments:**
> **username_1**: Cross-posted from https://mathoverflow.net/q/295997  
> **username_2**: There is Gap Exponential Time Hypothesis which implies that there is no $2^{o(n)}$ algorithm for this problem for some $\varepsilon, \delta>0$ and $a=\varepsilon |\phi|, b=\delta |\phi|$. See https://eccc.weizmann.ac.il/report/2016/128/ and https://arxiv.org/abs/1607.02986 .  

---

## 0 answers

