Consider any Boolean function $F(X_1,\ldots,X_N)$ that has more than $2^{-N^{d}}*2^N$ satisfying assignments and that can be expressed by a CNF formula with at most $N^{1+e}$ clauses for some $d>0$ and $e>0$ such that $d+e$ is less than $1$ (*). Then how many variables do we need to fix in order to satisfy $F$? In other words, what is the size of the shortest implicant of $F$? We show that for any $F$ satisfying (*), one can always find some short partial assignment on which $F$ evaluates to $1$ by fixing $\alpha N$ variables for some $\alpha>0$. That is, $F$ has an implicant of size $\le \alpha N$. On the other hand, a lower bound for such $\alpha$ is also shown in terms of $d$ and $e$.
We also discuss an algorithm for obtaining a short partial assignment, and we show a deterministic algorithm that finds a short partial assignment in $\widetilde{O}(2^{N^{\beta}})$-time for some $\beta<1$. Note that this can be used as a subexponential-time algorithm for solving the CNF-SAT problem for any CNF formula satisfying (*).
We now can show the exisitence of a short sat. partial assignment for any CNF with poly. number of clauses and 2^{-N^d}*2^N sat.
assignments for some d, 0 < d < 1.
Consider any Boolean function $F(X_1,\ldots,X_N)$ that has more than $2^{-N^{d}}$ satisfying assignments and that can be expressed by a CNF formula with at most $N^{1+e}$ clauses for some $d>0$ and $e>0$ such that $d+e$ is less than $1$ (*). Then how many variables do we need to fix in order to satisfy $F$? In other words, what is the size of the shortest implicant of $F$? We show that for any $F$ satisfying (*), one can always find some short partial assignment on which $F$ evaluates to $1$ by fixing $\alpha N$ variables for some $\alpha>0$. That is, $F$ has an implicant of size $\le \alpha N$. On the other hand, a lower bound for such $\alpha$ is also shown in terms of $d$ and $e$.
We also discuss an algorithm for obtaining a short partial assignment, and we show a deterministic algorithm that finds a short partial assignment in $\widetilde{O}(2^{N^{\beta}})$-time for some $\beta<1$. Note that this can be used as a subexponential-time algorithm for solving the CNF-SAT problem for any CNF formula satisfying (*).
Thanks to the referee of CCC13, we found a way to improve our result. Also we found some errors in the algorithmic version. These improvements/corrections have been made in the new version.
