Show simple item record

dc.contributor.advisor Vardi, Moshe Y.
dc.creatorDemopoulos, Demetrios D.
dc.date.accessioned 2009-06-04T06:47:52Z
dc.date.available 2009-06-04T06:47:52Z
dc.date.issued 2003
dc.identifier.urihttp://hdl.handle.net/1911/17587
dc.description.abstract This is an experimental investigation of three combinatorial problems. I examined the average-case complexity of random 3-SAT and of 3-Colorability of random graphs, and the satisfiability of random 1-3-HornSAT. All these problems, not only are interesting for their own sake, but also are of great practical importance since many other problems in computer science, engineering and other fields can be reduced to these. We systematically explored a large part of the problems' space, varying the size and the constrainedness of the instances, as well as the tools we used to solve them. We observed new phase transitions from polynomial to exponential complexity for random 3-SAT. A similar picture emerged for 3-Colorability. These experimental observations are important for understanding the inherent computational complexity of the problems. In the case of random 1-3-HornSAT, our findings suggest that there is a threshold at which the satisfiability changes from 1 to 0.
dc.format.extent 86 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
dc.title Probabilistic phenomena in random combinatorial problems
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Science
dc.identifier.citation Demopoulos, Demetrios D.. "Probabilistic phenomena in random combinatorial problems." (2003) Master’s Thesis, Rice University. http://hdl.handle.net/1911/17587.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record