MARC Record from University of Toronto

LEADER: 02413nam 2200265 4500
001 AAINR02609
005 20060110121825.5
008 060110s2005 onc|||||||||||||| ||eng d
020 $a049402609X
039 $fws
100 1 $aKolokolova, Antonina.
245 10 $aSystems of bounded arithmetic from descriptive complexity.
260 $c2005.
300 $a188 leaves.
502 $aThesis (Ph.D.)--University of Toronto, 2005.
506 $aElectronic version licensed for access by U. of T. users.
510 0 $aSource: Dissertation Abstracts International, Volume: 66-06, Section: B, page: 3232.
520 $aIn this thesis we discuss a general method of constructing systems of bounded arithmetic from descriptive complexity logics of known complexity. We discuss the conditions under which the resulting systems capture the same complexity class in the bounded arithmetic setting as the corresponding logic in the descriptive complexity setting. Our method works for small complexity classes (P and below) which have simple proofs of closure under complementation. Additionally, we require proofs of membership and co-membership for instances of decision problems to be constructible within the same complexity class.Based on this general theorem, we discuss systems of arithmetic for classes P and NL. We also give a system of arithmetic for SL, although the definability theorem for SL is weaker.More formally, given a logic L capturing complexity class C, the corresponding second-order system V-L of arithmetic consists of a system for AC 0 together with comprehension over L-formulae. If the class is provably in V-L closed under AC 0 reductions and every formula or its (possibly semantic) negation can be witnessed in C, then the resulting system captures C.
590 $aENGI copy differs in paging: vii, 155 l.
653 $aComputer Science.
856 41 $uhttp://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=232674&T=F$yConnect to resource
949 $aOnline resource 232674$wASIS$c1$i5656870-2001$lONLINE$mE_RESOURCE$rY$sY$tE_RESOURCE$u16/1/2006
949 $atheses COMPS 2005 Ph.D. 11949$wALPHANUM$c1$i31761061905964$lTHESES$mGERSTEIN$rY$sY$tBOOK$u16/1/2006
949 $aT PhD Ko$wLC$c1$i31761063316087$lSTACKS$mENGI_CSCI$rY$sY$tTHESIS$u6/2/2006
949 $atheses COMPS 2005 Ph.D. 11949$wALPHANUM$c1$i31761054831201$lMICROTEXT$mMEDIA_COMM$rY$sY$tMICROFORM$u24/1/2006$o.PUBLIC.