Exact algorithms for MAX-2SAT and MAX-3SAT via multidimensional matrix multiplication

Abstract

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.