Check nearby libraries
Buy this book
In this thesis, we present some results in computational complexity. We consider two approaches for showing that #P has polynomial-size circuits. These approaches use ideas from the interactive proof for #3-SAT. We show that these approaches fail. We discuss whether there are instance checkers for languages complete for the class of approximate counting problems. We provide evidence that such instance checkers do not exist. We discuss the extent to which proofs of hierarchy theorems are constructive. We examine the problems that arise when trying to make the proof of Fortnow and Santhanam's nonuniform BPP hierarchy theorem more constructive.
Check nearby libraries
Buy this book
Showing 2 featured editions. View all 2 editions?
Edition | Availability |
---|---|
1 |
aaaa
Libraries near you:
WorldCat
|
2 |
zzzz
Libraries near you:
WorldCat
|
Book Details
Edition Notes
Thesis (M.Sc.)--University of Toronto, 2005.
Electronic version licensed for access by U. of T. users.
Source: Masters Abstracts International, Volume: 44-01, page: 0394.
GERSTEIN MICROTEXT copy on microfiche (1 microfiche).
The Physical Object
ID Numbers
Community Reviews (0)
Feedback?January 24, 2010 | Edited by WorkBot | add more information to works |
December 11, 2009 | Created by WorkBot | add works page |