Revision #1 Authors: Daniel Kane, Osamu Watanabe

Accepted on: 22nd April 2014 23:40

Downloads: 1051

Keywords:

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.

TR13-176 Authors: Daniel Kane, Osamu Watanabe

Publication: 10th December 2013 04:25

Downloads: 2516

Keywords:

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.