Consistency in nondeterministic storage

摘要

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.