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* 1 edition

GL*
Steven Perron

Read

No readable version available.

Lists

You could add GL* to a list if you log in.
Darn it. 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

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

Pagination
50 leaves.
Number of pages
50

ID Numbers

Open Library
OL20238105M
ISBN 10
0494021764

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