University of Illinois Urbana-Champaign

Uniformity and bounded arithmetic below P

Parra, Carlos Mario

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/20189

Description

Title
Uniformity and bounded arithmetic below P
Author(s)
Parra, Carlos Mario
Issue Date
1996
Doctoral Committee Chair(s)
Jockusch, Carl G., Jr.
Department of Study
Mathematics
Discipline
Mathematics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Mathematics
Language
eng
Abstract
  • We study some of the complexity classes below P and, in particular, we concentrate on $AC\sp0\subseteq NC\sp1\subseteq L=$ LogSpace. We also study the nondeterministic classes $NAC\sp{i}$ and $NNC\sp{i},$ for $i\ge0,$ which are the counterparts to the more familiar class NP. In the final part of this work we characterize the so-called Steven's Class $SC=\bigcup\sb{i\ge1}Sc\sp{i}.$
  • "We start by proving that certain basic arithmetic operations such as Count, Multiplication, Multiple Addition, Sorting, etc. can be carried out in Uniform-$NC\sp1$ and that similar results hold in the class Uniform-$AC\sp0$ when dealing with sufficiently ""small"" numbers. The proofs are carried out by using algebraic characterizations of the previous classes as developed, for example, in (C14) and (CT2)."
  • We continue with the classes $NAC\sp0\subseteq NNC\sp1\subseteq\cdots\subseteq NP$ introduced in (Ta2) and prove that, in fact, all of them coincide and therefore are equal to NPolyTime.
  • Finally, we move further up and consider the complexity class SC as defined in (Co2). We introduce the notion of Extended k-Bounded Recursion on Notation $(E\sb{k}BRN)$ and prove that the class $SC\sp{k}$ equals the closure of the set of basic functions INITIAL (see for example, (CT2)), under composition, CRN and $E\sb{k}BRN.$
Type of Resource
text
Permalink
http://hdl.handle.net/2142/20189
Copyright and License Information
Copyright 1996 Parra, Carlos Mario

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mathematics