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 |
zzzz
Libraries near you:
WorldCat
|
2 |
aaaa
Libraries near you:
WorldCat
|
Book Details
Edition Notes
Source: Masters Abstracts International, Volume: 44-01, page: 0394.
Thesis (M.Sc.)--University of Toronto, 2005.
Electronic version licensed for access by U. of T. users.
ROBARTS MICROTEXT copy on microfiche.
The Physical Object
ID Numbers
Community Reviews (0)
Feedback?History
- Created October 21, 2008
- 2 revisions
Wikipedia citation
×CloseCopy and paste this code into your Wikipedia page. Need help?
December 15, 2009 | Edited by WorkBot | link works |
October 21, 2008 | Created by ImportBot | Imported from University of Toronto MARC record. |