Show simple item record

dc.contributor.authorPetkevich, Yevghenieng
dc.date.accessioned2015-08-24T12:22:54Z
dc.date.available2015-08-24T12:22:54Z
dc.date.issued2015-06-01
dc.date.submitted2015-06-01eng
dc.identifier.urihttps://hdl.handle.net/1956/10348
dc.description.abstractIn 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.extent713880 byteseng
dc.format.mimetypeapplication/pdfeng
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.rightsCopyright the Author. All rights reservedeng
dc.subjectMatriseregningNob
dc.subjectNumeriske algoritmerNob
dc.subjectMAX-2SATeng
dc.subjectMAX-3SATeng
dc.subjectmatrix multiplicationeng
dc.subjectcube multiplicationeng
dc.subjectalgorithmseng
dc.titleExact algorithms for MAX-2SAT and MAX-3SAT via multidimensional matrix multiplicationen_US
dc.typeMaster thesis
dc.description.degreeMaster i Informatikken_US
dc.description.localcodeMAMN-INF
dc.description.localcodeINF399
dc.subject.realfagstermerhttp://data.ub.uio.no/realfagstermer/c010079
dc.subject.realfagstermerhttp://data.ub.uio.no/realfagstermer/c005975
dc.subject.nus754199eng
fs.subjectcodeINF399


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record