Check nearby libraries
Buy this book
In recent years, there has been considerable research exploring connections between propositional proof systems, theories of bounded arithmetic, and complexity classes. We know that NC1 corresponds to G*0 and that P corresponds to G1 , but no proof system corresponding to a complexity class between NC1 and P has been defined.In this work, we construct a proof system GL, which corresponds to L. Connections to the theory VL (Zambella's Sp0 - rec) are also considered. GL is defined by restricting cuts in the system G1 . The first restriction is syntactic: the cut formulas have to be Sigma CNF(2), which is a new class of formulas. Unfortunately that is not enough; the free variables in cut formulas must be restricted to parameter variables. We prove that GL corresponds to VL by translating theorems of VL into tautologies with small GL proof.
Check nearby libraries
Buy this book
Showing 1 featured edition. View all 1 editions?
Edition | Availability |
---|---|
1 |
aaaa
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: 0404.
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 |