ECCC-Report TR13-176https://eccc.weizmann.ac.il/report/2013/176Comments and Revisions published for TR13-176en-usTue, 22 Apr 2014 23:40:18 +0300
Revision 1
| A Short Implicant of CNFs with Relatively Many Satisfying Assignments |
Osamu Watanabe,
Daniel Kane
https://eccc.weizmann.ac.il/report/2013/176#revision1Consider 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 (*).
Tue, 22 Apr 2014 23:40:18 +0300https://eccc.weizmann.ac.il/report/2013/176#revision1
Comment 1
| revision |
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2013/176#comment1Thanks 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.Tue, 22 Apr 2014 16:16:25 +0300https://eccc.weizmann.ac.il/report/2013/176#comment1
Paper TR13-176
| A Short Implicant of CNFs with Relatively Many Satisfying Assignments |
Osamu Watanabe,
Daniel Kane
https://eccc.weizmann.ac.il/report/2013/176Consider 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 (*).
Tue, 10 Dec 2013 04:25:54 +0200https://eccc.weizmann.ac.il/report/2013/176