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 | |