Institutional Scholarship

COMPLEXITY OF COUNTING

Show simple item record

dc.contributor.advisor Lindell, Steven
dc.contributor.author Cao, Chang
dc.date.accessioned 2013-06-03T19:30:31Z
dc.date.available 2013-06-03T19:30:31Z
dc.date.issued 2013
dc.identifier.uri http://hdl.handle.net/10066/10844
dc.description.abstract In this paper, we consider two problems related to counting problems in complexity theory. First, we use the reachability method to prove that nondeterministic logarithm space is closed under complement. Then, we consider the graph matching problem and explain the FKT algorithm which counts the number of the perfect matchings in a planar graph in polynomial time. The general result of counting perfect matchings is known as the PERMANENT problem, which Valiant proved to be #P-complete.
dc.description.sponsorship Haverford College. Department of Computer Science
dc.language.iso eng
dc.rights.uri http://creativecommons.org/licenses/by-nc/3.0/us/
dc.subject.lcsh Counting -- Mathematical models
dc.subject.lcsh Computational complexity
dc.title COMPLEXITY OF COUNTING
dc.type Thesis
dc.rights.access Open Access


Files in this item

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by-nc/3.0/us/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc/3.0/us/

Search


Browse

My Account