Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Automatic Enumeration of Intervals of Partial Co-Clones
Linköping University, Department of Computer and Information Science. (TCSLAB)
2016 (English)Independent thesis Advanced level (degree of Master (One Year)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Computer scientists are curious about the complexity relationship between different kinds of NP-complete SAT problems. In order to understand the complexity relationship between SAT problems, we decided to correspond SAT problems to a kind of algebra called partial co-clones. Each SAT problem can be represented by a set of Boolean relations. Partial co-clones are Boolean relations enumerated under quantifier-free primitive positive definition. If SAT(R2) is included in SAT(R1)’s partial co-clones, SAT(R1) cannot be solved faster than SAT(R2). We used this kind of relationship to get a partial order of the worst-case time complexity of SAT problems. Partial co-clones are complicated, and we do not really understand the structure of partial co-clones. Therefore, it would have been easier to explore parts of their structures automatically with the help of current computers. We strived to develop a scalable efficient program exploiting parallel computers. We started with exploring sequential optimization methods including data structure design, Depth First Search combination, Inverse SAT, and tried to partition the searching process equally to each computing node. We proposed an easy but efficient, scalable implementation that could handle problem size less than O(280) with memory cost equal to O(n). Given enough computing nodes, we could achieve performance close to linear speedup.

Place, publisher, year, edition, pages
2016. , 38 p.
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:liu:diva-127982ISRN: LIU-IDA/LITH-EX-A--16/012--SEOAI: oai:DiVA.org:liu-127982DiVA: diva2:928088
Subject / course
Computer science
Presentation
2016-03-09, Alan Turing, Linköping University 581 83, Linkoping, 13:15 (English)
Supervisors
Examiners
Available from: 2016-05-17 Created: 2016-05-14 Last updated: 2016-05-17Bibliographically approved

Open Access in DiVA

Clones(1291 kB)31 downloads
File information
File name FULLTEXT01.pdfFile size 1291 kBChecksum SHA-512
f4aa7a51c6df208563f2481510aab517b0848722c6ea4c38c0d9463a25f5670566c3f8ce75429468bbbba76f7c21a3db6d885bf368f3875d6e7b493c9e5ad6c3
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Shih, Adam
By organisation
Department of Computer and Information Science
Other Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 31 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 171 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf