作者：
Pratt, KevinNYU
Courant Inst Math Sci New York NY 10012 USA
We give a short proof that Strassen's asymptotic rank conjecture implies that for every epsilon > 0 there exists a (3/2(2/3) + epsilon)(n) -time algorithm for set cover on a universe of size n with sets of boun...
详细信息
ISBN:
(纸本)9798400703836
We give a short proof that Strassen's asymptotic rank conjecture implies that for every epsilon > 0 there exists a (3/2(2/3) + epsilon)(n) -time algorithm for set cover on a universe of size n with sets of bounded size. This strengthens and simplies a recent result of Bjorklund and Kaski that Strassen's asymptotic rank conjecture implies that the set cover conjecture is false. From another perspective, we show that the set cover conjecture implies that a particular family of tensorsT(n) epsilon C-N circle times C-N circle times C-N has asymptotic rank greater than N-1.08. Furthermore, if one could improve a known upper bound of 8(n) on the tensor rank of T-n to 2/ 9 center dot n 8n for any n, then the set cover conjecture is false.
We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is the first algorithm which approximat...
详细信息
ISBN:
(纸本)9783939897354
We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is the first algorithm which approximates #k-SAT for any k >= 3 within a running time that is not only non-trivial, but also significantly better than that of the currently fastest exact algorithms for the problem. More precisely, our algorithm is a randomized approximation scheme whose running time depends polynomially on the error tolerance and is mildly exponential in the number n of variables of the input formula. For example, even stipulating sub-exponentially small error tolerance, the number of solutions to 3-CNF input formulas can be approximated in time O(1.5366(n)). For 4-CNF input the bound increases to O(1.6155(n)). We further show how to obtain upper and lower bounds on the number of solutions to a CNF formula in a controllable way. Relaxing the requirements on the quality of the approximation, on k-CNF input we obtain significantly reduced running times in comparison to the above bounds.
The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane [7]. Analyzing its running time is much easier for input formulas with a unique satisfying assignment. I...
详细信息
ISBN:
(纸本)9783959770408
The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane [7]. Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify Hertli's 2011 analysis [1] for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. Combining this with a result by Hertli from 2014 [2], in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.
PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order;each variable is then set randomly to 0 or 1, unless the correct value can be inferr...
详细信息
ISBN:
(纸本)9781665420556
PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order;each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution;or being implied by a small set of clauses). We show that PPSZ performs exponentially better than previously known, for all k >= 3. For Unique-3-SAT we bound its running time by O(1.306973(n)), which is somewhat better than the algorithm of Hansen, Kaplan, Zamir, and Zwick. All improvements are achieved without changing the original PPSZ. The core idea is to pretend that PPSZ does not process the variables in uniformly random order, but according to a carefully designed distribution. We write "pretend" since this can be done without any actual change to the algorithm.(1 2)
We show that for k >= 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k >= 5, there is a strictly inc...
详细信息
We show that for k >= 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k >= 5, there is a strictly increasing function f : [0, 1] -> R with f (0) = 0 that has the following property. If F is a k-CNF formula over n variables and vertical bar sat(F)vertical bar = 2(delta n) solutions, then PPSZ finds a satisfying assignment with probability at least 2(-ck n-o(n) + f(delta)n).Here, 2(-ck n-o(n)) is the success probability proved by Paturi et al. [11] for k-CNF formulas with a unique satisfying assignment. Our proof rests on a combinatorial lemma: given a set S subset of {0.1}(n), we can partition {0.1}(n) into subcubes such that each subcube B contains exactly one element of S. Such a partition B induces a distribution on itself, via Pr[B] = vertical bar B vertical bar/2(n) for each B is an element of B. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case (min(S:vertical bar S vertical bar =s) max(B) H(B)) is achieved if S is a Hamming ball. This lemma implies that every set S of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.
In this paper, we achieve three goals. First, we simplify Hertli's 2011 analysis [1] for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ f...
详细信息
ISBN:
(纸本)9783959770408
In this paper, we achieve three goals. First, we simplify Hertli's 2011 analysis [1] for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF *** this with a result by Hertli from 2014 [2], in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.
暂无评论