Click here to skip to this page's main content.

New to the Open Library? — Learn how it works
Last edited by WorkBot
January 24, 2010 | History

GL*: A propositional proof system for logspace 1 edition

GL*: A propositional proof system for logspace
Steven Perron


No readable version available.


You could add GL*: A propositional proof system for logspace to a list if you log in.
Uh oh. There's no description for this book yet. Can you help?
There is only 1 edition record, so we'll show it here...  •  Add edition?

GL*: A propositional proof system for logspace.

Published 2005 .
Written in English.

About the 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.

Edition Notes

Source: Masters Abstracts International, Volume: 44-01, page: 0404.

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

50 leaves.
Number of pages

ID Numbers

Open Library

History Created December 11, 2009 · 2 revisions Download catalog record: RDF / JSON

January 24, 2010 Edited by WorkBot add more information to works
December 11, 2009 Created by WorkBot add works page