Complexity classes: Tree models, operators and oracles.
Item
-
Title
-
Complexity classes: Tree models, operators and oracles.
-
Identifier
-
AAI9521313
-
identifier
-
9521313
-
Creator
-
Sharma, Kiron.
-
Contributor
-
Adviser: E. Zachos
-
Date
-
1995
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
Our fundamental machine model is a NDTM. We consider complexity classes involving polynomial time.;Tree models. All the possible computation paths of a NDTM can be represented in the form of a tree structure. In general we have a different length for each path and a different fan-out at each internal node.;We present simplified padding and extension techniques used in order to obtain a uniform model (complete binary computational trees) for: (a) PP Computations, (b) #P Computations and (c) Computations belonging to sub-classes of the class #P. Similar techniques can be extended to most complexity classes within PH.;Operators. We consider complexity class operators corresponding to nondeterministic, probabilistic and counting classes. The characterization of classes in terms of operators is closely related to the oracle characterization. We study the calculus of operators and in the process we identify some interesting properties and the behavior of certain widely used operators applied on complexity classes. We identify operators which yield unexpected collapse results, when these operators are assumed to satisfy certain properties. The goal is to argue about complexity class inclusions using algebraic techniques. We introduce two new sensible operators corresponding to the classes (NP {dollar}\cap{dollar} co-NP) and ZPP respectively. The operator "ZP{dollar}\cdot{dollar}" provides us with a medium to study the Las-Vegas version of complexity classes. It turns out that the well known Graph Isomorphism problem is in the Las-Vegas version of NP i.e., the class ZP{dollar}\cdot{dollar}NP, exactly as the primality problem is in the Las-Vegas version of P i.e., ZPP.;Oracles. We show that a BPP oracle is not very powerful. Among other things, we prove: NP using a BPP oracle is (lower than) contained in ZPP using a D{dollar}\sp{lcub}\rm P{rcub}{dollar} oracle. We use quantifiers and combinatorial techniques to prove this result.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
