GL*: A propositional proof system for logspace.

  • 0 Ratings
  • 0 Want to read
  • 0 Currently reading
  • 0 Have read
GL*: A propositional proof system for logspa ...
Steven Perron
Not in Library

My Reading Lists:

Create a new list

Check-In

×Close
Add an optional check-in date. Check-in dates are used to track yearly reading goals.
Today

  • 0 Ratings
  • 0 Want to read
  • 0 Currently reading
  • 0 Have read

Buy this book

Last edited by WorkBot
December 15, 2009 | History

GL*: A propositional proof system for logspace.

  • 0 Ratings
  • 0 Want to read
  • 0 Currently reading
  • 0 Have read

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.

Publish Date
Language
English
Pages
50

Buy this book

Edition Availability
Cover of: GL*:  A propositional proof system for logspace.

Add another edition?

Book Details


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

Pagination
50 leaves.
Number of pages
50

ID Numbers

Open Library
OL19214732M
ISBN 10
0494021764

Community Reviews (0)

Feedback?
No community reviews have been submitted for this work.

Lists

This work does not appear on any lists.

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
December 15, 2009 Edited by WorkBot link works
October 21, 2008 Created by ImportBot Imported from University of Toronto MARC record.