Consistency in nondeterministic storage (Q1060847)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Consistency in nondeterministic storage |
scientific article; zbMATH DE number 3909743
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Consistency in nondeterministic storage |
scientific article; zbMATH DE number 3909743 |
Statements
Consistency in nondeterministic storage (English)
0 references
1984
0 references
A generalization of nondeterminism, called consistent nondeterminism, is investigated. It is shown that consistent storage is exponentially more powerful than ordinary storage. Simultaneous classes obtained by bounding both amount of storage and amount of consistent nondeterminism are characterized in terms of time bounded nondeterministic complexity classes. Relationships between consistent storage complexity classes and certain oracle complexity classes are investigated.
0 references
nondeterminism
0 references
complexity classes
0 references
oracle
0 references
0.8580473
0 references
0.8580473
0 references
0.8474044
0 references
0.8450283
0 references
