A note on the almost-everywhere hierarchy for nondeterministic time

Eric Allender; Richard Beigel; Ulrich Hertrampf; Steven Homer

doi:10.1007/3-540-52282-4_27

Back

A note on the almost-everywhere hierarchy for nondeterministic time

Book chapter

Peer reviewed

A note on the almost-everywhere hierarchy for nondeterministic time

Eric Allender, Richard Beigel, Ulrich Hertrampf and Steven Homer

STACS 90, pp.1-11

Lecture Notes in Computer Science, Springer Berlin Heidelberg

06/06/2005

DOI: https://doi.org/10.1007/3-540-52282-4_27

Abstract

Deterministic Time

Monotone Nondecreasing

Infinite Subset

Turing Machine

Random Access Machine

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

Metrics

10 Record Views

Details

Title: A note on the almost-everywhere hierarchy for nondeterministic time
Creators: Eric Allender
Richard Beigel
Ulrich Hertrampf
Steven Homer
Publication Details: STACS 90, pp.1-11
Date published: 06/06/2005
Series: Lecture Notes in Computer Science
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Book chapter
Identifiers: 991031654528604646