GL*
Subtitle: a propositional proof system for logspace.
Published: 2005
Language: eng
Number of pages: 50
Description: 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.
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).