Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:liu:diva-127982ISRN: LIU-IDA/LITH-EX-A--16/012--SEOAI: diva2:928088
Subject / course
Computer science
2016-03-09, Alan Turing, Linköping University 581 83, Linkoping, 13:15 (English)
Available from: 2016-05-17 Created: 2016-05-14 Last updated: 2016-05-17Bibliographically approved

Open Access in DiVA

Clones(1291 kB)15 downloads
File information
File name FULLTEXT01.pdfFile size 1291 kBChecksum SHA-512
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: 15 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

Total: 135 hits
ReferencesLink to record
Permanent link

Direct link