Title: Non-uniform and nondeterministic reductions in structural complexity
Abstract: We consider two different types of reductions, polynomial-time non-uniform many-one reductions and reductions which use nondeterminism. We study the properties of nonuniform many-one reductions and the complete sets they generate in well known complexity classes. We show for exponential time that the sets complete under polynomial-time many-one reductions with one bit of advice are different from the sets that are complete under polynomial-time many-one reductions with no advice. We bound the size of this set of complete languages by showing that every set that is complete under polynomial-time non-uniform reductions with small advice is complete under polynomial-time Turing reductions for exponential time. We study the behavior of these non-uniform reductions in nondeterministic complexity classes. Most notably we show that the many-one complete sets with one bit of advice within the delta levels of the polynomial hierarchy are also complete using polynomial-time non-adaptive reductions. While it is known that complete sets under non-uniform reductions are complete under non-uniform length increasing reductions within nondeterministic classes, we strengthen these results. We give a precise bound on the amount of advice needed to create length increasing reductions and give evidence that this is optimal.
For nondeterministic reductions we build on current techniques to show that under reasonable hypotheses there are sets within polynomial space which are complete under nondeterministic polynomial time reductions, but not under deterministic polynomial time reductions. We generalize the NP-machine hypothesis to create a hierarchy of problems which require increasing amounts of nondeterminism to be complete in polynomial space, creating a reverse polynomial hierarchy within PSPACE.
Publication Year: 2008
Publication Date: 2008-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot