dc.contributor.author Petkevich, Yevgheni eng dc.date.accessioned 2015-08-24T12:22:54Z dc.date.available 2015-08-24T12:22:54Z dc.date.issued 2015-06-01 dc.date.submitted 2015-06-01 eng dc.identifier.uri https://hdl.handle.net/1956/10348 dc.description.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. en_US dc.format.extent 713880 bytes eng dc.format.mimetype application/pdf eng dc.language.iso eng eng dc.publisher The University of Bergen en_US dc.rights Copyright the Author. All rights reserved eng dc.subject Matriseregning Nob dc.subject Numeriske algoritmer Nob dc.subject MAX-2SAT eng dc.subject MAX-3SAT eng dc.subject matrix multiplication eng dc.subject cube multiplication eng dc.subject algorithms eng dc.title Exact algorithms for MAX-2SAT and MAX-3SAT via multidimensional matrix multiplication en_US dc.type Master thesis dc.description.degree Master i Informatikk en_US dc.description.localcode MAMN-INF dc.description.localcode INF399 dc.subject.realfagstermer http://data.ub.uio.no/realfagstermer/c010079 dc.subject.realfagstermer http://data.ub.uio.no/realfagstermer/c005975 dc.subject.nus 754199 eng fs.subjectcode INF399
﻿