On Some Central Problems in Computational Complexity

Other Titles
Abstract

In this thesis we examine some of the central problems in the theory of computational complexity, like the trade-offs between time and memory, the power of nondeterminism and parallelism, and the speed gained by adding new operations to random access machines. Our main result is the cahracterization of the power of multiplication in random access acceptors: we show, in Chapter 3, that for such models nondeterministic and deterministic computations are polynomially related and that there is a polynomial relationship between the amount of time required for acceptance by random access machines with multiplication, and the amount of tape required by Turing machines. Thus, the additional power gained by using multiplication is the same as that of memory over time (if any). We derive similar results for some other interesting instruction sets. We also have some results for probabilistic and nondeterministic computations: we define threshold machines and show how probabilistic Turing machines may simulate them, and exhibit a set of complete problems for threshold machines. For nondeterministic computations, we present a hierarchy of the elementary recursive languages obtained by polynomially bounded quantification over objects of higher and higher type, which represent nondeterministic time bounded computations with larger and larger bounds. Finally, we discuss some deterministic computations, and conclude with a look at some open problems.

Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
1975-01
Publisher
Cornell University
Keywords
computer science; technical report
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-224
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
technical report
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record