# GL*: A propositional proof system for logspace 1 edition

### Read

No readable version available.

### Borrow

Find a physical copy near you — powered by WorldCat

**help**?

##
**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 G*1 , 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 G*1 . 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

## Pagination |
50 leaves. |

## Number of pages |
50 |

### ID Numbers

## Open Library |
OL19214732M |

## 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 |