Bounded Width Dichotomies in Constraint Satisfaction Problems
dc.contributor.advisor | Laflamme, Claude | |
dc.contributor.advisor | Woodrow, Robert E. | |
dc.contributor.author | Liprandi, Maximiliano | |
dc.contributor.committeemember | Cavers, Michael S. | |
dc.contributor.committeemember | Cockett, J. Robin B. | |
dc.contributor.committeemember | Bonato, Anthony | |
dc.date | 2018-11 | |
dc.date.accessioned | 2018-06-11T19:44:28Z | |
dc.date.available | 2018-06-11T19:44:28Z | |
dc.date.issued | 2018-06-07 | |
dc.description.abstract | In this thesis we examine the connection between structures with bounded width, polymorphisms and pebble games. There has been extensive work on trying to prove the dichotomy conjecture for finite structures, namely, the Constraint Satisfaction Problem (CSP) of a finite structure is either in P or NP-complete. We are interested in finding classes in which a stronger dichotomy exists; namely, where every structure has either bounded width or a hard CSP. We call this kind of dichotomy a bounded width dichotomy. We will investigate properties of polymorphisms of structures with bounded width, and use this to look at classes of directed graphs with a bounded width dichotomy. | en_US |
dc.identifier.citation | Liprandi, M. (2018). Bounded Width Dichotomies in Constraint Satisfaction Problems (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/31986 | en_US |
dc.identifier.doi | http://dx.doi.org/10.11575/PRISM/31986 | |
dc.identifier.uri | http://hdl.handle.net/1880/106758 | |
dc.language.iso | eng | |
dc.publisher.faculty | Graduate Studies | |
dc.publisher.faculty | Science | |
dc.publisher.institution | University of Calgary | en |
dc.publisher.place | Calgary | en |
dc.rights | University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission. | |
dc.subject.classification | Education--Mathematics | en_US |
dc.title | Bounded Width Dichotomies in Constraint Satisfaction Problems | |
dc.type | doctoral thesis | |
thesis.degree.discipline | Mathematics & Statistics | |
thesis.degree.grantor | University of Calgary | |
thesis.degree.name | Doctor of Philosophy (PhD) | |
ucalgary.item.requestcopy | true |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- ucalgary_2018_liprandi_maximiliano.pdf
- Size:
- 777.7 KB
- Format:
- Adobe Portable Document Format
- Description:
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.74 KB
- Format:
- Item-specific license agreed upon to submission
- Description: