Almost-everywhere complexity hierarchies for nondeterministic time

Eric Allender; Richard Beigel; Ulrich Hertrampf; Steven Homer

doi:10.7282/t3-v26s-v211

Back

Almost-everywhere complexity hierarchies for nondeterministic time

Technical documentation

Open access

Almost-everywhere complexity hierarchies for nondeterministic time

Eric Allender, Richard Beigel, Ulrich Hertrampf and Steven Homer

Rutgers University

1993

DOI:

https://doi.org/10.7282/t3-v26s-v211

Abstract

We present an a.e. complexity hierarchy for nondeterministic time, and show that it is essentially the best result of this sort that can be proved using relativizable proof techniques.

Files and links (2)

pdf

lcsr-tr-189228.97 kBDownload View

Technical Documentation Open Access

url

Report an accessibility issueView

Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

189 File downloads

85 Record Views

Details

Title: Subtitle: Almost-everywhere complexity hierarchies for nondeterministic time
Creators: Eric Allender (Author) - Computer Science (New Brunswick)
Richard Beigel (Author) - Yale University
Ulrich Hertrampf (Author) - Bayerische Julius-Maximilians-Universität Würzburg
Steven Homer (Author) - Boston University
Date published: 1993
Publisher: Rutgers University
Number of pages: 1 online resource (28 pages)
Academic Unit: School of Arts and Sciences; Computer Science (SAS)
Language: English
Resource Type: Technical documentation
Comment: Technical report LCSR-TR-189
Identifiers: 991031550042204646