Timeline for What is wrong with this seeming contradiction with a paper about AND-compression of SAT?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2014 at 8:53 | comment | added | user12859 | Er, I used the wrong words in my previous comment. $\:$ I meant "by replacing each occurrence in a given SAT-instance of the n-th distinct variable to appear in that SAT-instance with $x_n$". $\:$ Your last two sentences are correct. $\;\;\;\;$ | |
| Jun 11, 2014 at 8:43 | comment | added | elluser | OK. I meant the instances to be completely independent. The satisfiability of x_i doesn't depend in no way of x_j. If you take $t$ DIMACS instances from the SAT competition, relabel the variables, you can't sufficiently compress them with say gzip. This doesn't mean efficient SAT compression can't work. | |
| Jun 11, 2014 at 8:10 | comment | added | user12859 | One can just canonicalize variable names, by replacing each instance in a given clause of the n-th distinct variable to appear in that clause with $x_n$. $\;$ | |
| Jun 11, 2014 at 8:07 | comment | added | elluser | Why the disjointless is irrelevant? Appears to me this make things harder since there are no relations between the instances. | |
| Jun 11, 2014 at 8:01 | comment | added | user12859 | The disjointness of the variables is irrelevant. $\:$ I suspect that there are no known non-trivial algorithms for AND-compression of such distributions and no known (other) seemingly unlikely consequences of the existence of an efficient AND-compression algorithm for such distributions. $\;\;\;\;$ | |
| Jun 11, 2014 at 7:50 | comment | added | elluser | I mean efficient minimization/compression. Certainly solving gives O(1) compression. | |
| Jun 10, 2014 at 20:10 | comment | added | user12859 | "since this will solve" what "by sufficient calls to the minimization"? $\:$ One can compress every single SAT instance (though not necessarily efficiently); just replace "all of the input SAT-instances are satisfiable. If they all are" in my answer with "the input SAT-instance is satisfiable. If it is". $\;\;\;\;$ | |
| Jun 10, 2014 at 20:10 | comment | added | user12859 | Those are compressible (though not necessarily efficiently); just use the algorithm that I gave. $\:$ The only relation between this problem circuit minimization that I see is the fact that, depending on whether not circuits are required to actually map each input to a node, SAT may be efficiently reducible to circuit minimization. $\;\;\;\;$ | |
| Jun 10, 2014 at 12:44 | comment | added | elluser | Thank you, this helped. Are these compressable: take $t$ (as large as possible) instances on disjoint variables of the same size. The instances are state of the art random 3-SAT. Since they are on disjoint variables, circuit minimization doesn't work. One can't compress every single SAT instances, since this will solve it by sufficient calls to the minimization. | |
| Jun 9, 2014 at 19:01 | history | answered | user12859 | CC BY-SA 3.0 |