Exact algorithms for MAX-2SAT and MAX-3SAT via multidimensional matrix multiplication
Petkevich, Yevgheni · NORA - Norwegian Open Research Archives · 2015
In this thesis it is showed how an \\(O(n^{4-\\epsilon})\\) algorithm for the cube multiplication problem (that is defined in the thesis) would imply a faster than naive \\(O^{*}(2^{n(1-\\frac{\\epsilon}{4})})\\) algorithm for the MAX-3SAT problem; this algorithm for MAX-3SAT is a generalization of the algorithm for the MAX-2SAT problem which was proposed by Ryan Williams; and cube multiplication, in turn, is defined as a generalization of the matrix multiplication problem for three-dimensional arrays. Approaches to find a faster than naive algorithm for cube multiplication are considered. Though no such algorithm was found using these approaches, it is showed how a variant of the Strassen algorithm for matrix multiplication could be found using the same approaches. Implementations of these approaches using computer programming and results of computational experiments are discussed.