Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-176 | 22nd April 2014 23:40

A Short Implicant of CNFs with Relatively Many Satisfying Assignments

RSS-Feed




Revision #1
Authors: Daniel Kane, Osamu Watanabe
Accepted on: 22nd April 2014 23:40
Downloads: 653
Keywords: 


Abstract:

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 (*).



Changes to previous version:

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.


Paper:

TR13-176 | 8th December 2013 00:22

A Short Implicant of CNFs with Relatively Many Satisfying Assignments





TR13-176
Authors: Daniel Kane, Osamu Watanabe
Publication: 10th December 2013 04:25
Downloads: 1407
Keywords: 


Abstract:

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 (*).


Comment(s):

Comment #1 to TR13-176 | 22nd April 2014 16:16

revision

Authors: Osamu Watanabe
Accepted on: 22nd April 2014 16:16
Keywords: 


Comment:

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.




ISSN 1433-8092 | Imprint