Simplicity, Relativizations and Nondeterminism

Publisher Website
Google Scholar
Abstract
Relativizations of complexity classes in which simple sets exist are considered. A recursive oracle is constructed relative to which a simple set exists for NP. Some other general theorems are proven, showing that the time bounds are not a crucial hypothesis; bounds on the way in which the oracle is accessible, namely the number of queries and/or the number of nondeterministic steps, are shown to be the fundamental hypothesis. As a result, simple sets are shown to exist in many different relativized complexity classesPeer ReviewedPostprint (published version

This publication has 9 references indexed in Scilit: