Some results in computational complexity.
Published: 2005
Language: eng
Number of pages: 64
Description: 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.
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.