eCommons

 

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