Show simple item record

dc.contributor.authorFinkelstein, Jeffreyen_US
dc.date.accessioned2017-03-06T20:10:15Z
dc.date.available2017-03-06T20:10:15Z
dc.date.issued2017
dc.identifier.urihttps://hdl.handle.net/2144/20720
dc.description.abstractComputational complexity theory studies which computational problems can be solved with limited access to resources. The past fifty years have seen a focus on the relationship between intractable problems and efficient algorithms. However, the relationship between inherently sequential problems and highly parallel algorithms has not been as well studied. Are there efficient but inherently sequential problems that admit some relaxed form of highly parallel algorithm? In this dissertation, we develop the theory of structural complexity around this relationship for three common types of computational problems. Specifically, we show tradeoffs between time, nondeterminism, and parallelizability. By clearly defining the notions and complexity classes that capture our intuition for parallelizable and sequential problems, we create a comprehensive framework for rigorously proving parallelizability and non-parallelizability of computational problems. This framework provides the means to prove whether otherwise tractable problems can be effectively parallelized, a need highlighted by the current growth of multiprocessor systems. The views adopted by this dissertation—alternate approaches to solving sequential problems using approximation, limited nondeterminism, and parameterization—can be applied practically throughout computer science.en_US
dc.language.isoen_US
dc.rightsAttribution-ShareAlike 4.0 Internationalen_US
dc.rights.urihttps://creativecommons.org/licenses/by-sa/4.0/
dc.subjectComputer scienceen_US
dc.subjectComputational complexityen_US
dc.subjectLimited nondeterminismen_US
dc.subjectNondeterminismen_US
dc.subjectParallelismen_US
dc.subjectParameterized complexityen_US
dc.titleParallelism with limited nondeterminismen_US
dc.typeThesis/Dissertationen_US
dc.date.updated2017-03-05T05:07:22Z
etd.degree.nameDoctor of Philosophyen_US
etd.degree.leveldoctoralen_US
etd.degree.disciplineComputer Scienceen_US
etd.degree.grantorBoston Universityen_US


This item appears in the following Collection(s)

Show simple item record

Attribution-ShareAlike 4.0 International
Except where otherwise noted, this item's license is described as Attribution-ShareAlike 4.0 International